堆排序？

01-31

給出一組關鍵字12 2 16 30 8 28 4 10 20 6 18對初始關鍵字排序，寫出按照堆排序演算法所建立的初始大頂堆
問題是，是按照順序每放進去一個就排一次序還是將全部都堆進去後排序？
老師在講題時和網上一些答案都偏向於第二種，可是堆排序不應該放進去一個就排序嗎

ps老師講的時候的答案是第一種做法，然後老師按照第二種講的，說答案錯了

從實現來看是這樣的：

第一種方法是先假設堆是空的，依次附加每個元素，由於堆的附加就是向上調整（不是排序，你不能用堆排序來實現堆排序）。相當於每個非根元素依次向上調整。

第二種方法是每個非葉子元素倒序向下調整。

複雜度是。。。好吧我記錯了，第二種是O(n)，比第一種低。

這是建堆的過程。但是一旦你有了一個堆，排序就簡單多了。重複（1）堆的頭尾互換（2）移除堆尾元素放到另一個地方（3）堆頭向下調整，直到堆為空。

首先你得知道什麼是「堆排序演算法」？

「每放進去一個就排一次序」也太可怕了，時間複雜度是……？

堆排序，是用堆這種數據結構對一組關鍵字排序。向堆中插入數據構建堆以及從堆中刪除數據利用堆輸出有序序列的時候都是有一個比較的過程的（n個元素都要進行比較，比較這個過程時間複雜度logn)，但比較不是說排序

堆排序其實是建樹的過程，你看完書再問問題。

如果目的是【寫出按照堆排序演算法所建立的初始大頂堆】，那兩種方法都是對的。

第一種是最開始有一個空的堆，然後一個一個的插入數字（參考《演算法導論》堆的插入操作）

第二種是最開始有一個數組，然後把這個數組建成一個大頂堆（參考《演算法導論》堆排序）

排序的操作是在建好堆之後的了。。

每次放一個就排序(其實是調整)是平衡二叉樹，放完了再排序(調整)是堆排序。我覺得你困擾在這裡，去買本王道數據結構看看吧。

堆排序是利用堆的特性來排序。

你不要用空間優化過的方式，把有序區無序區分開比較好理解。

第一步先建堆，就是從頭生成一個二叉樹。每次插入一個新元素都會對堆進行調整以維護堆性質。

第二步重複刪除堆頂根元素，並在每次刪除後調整堆使之保持堆性質。

用大堆的話，每次都是堆里最大值，這樣自然就排好序了。

剩下的就是一些具體的技巧了。