Heapsort問題

Question

由於堆是二叉樹和數組的組合，排序時整個堆是否保持完整樹的形式？

對於家庭作業的任務，我必須找出排序的每一步的堆和數組，並且我不確定樹的表示。

Answer 1

堆總是一個完全平衡的完全填充樹，它遵循堆不變 - 對於最小堆，節點的值始終大於或等於其每個子節點的值。

Heapsort從未排序的數據（O（n）時間）中創建一個堆，然後重複刪除堆的頂層元素（O（lg n）時間，因爲堆必須在每次移除時保留）並將其放入成陣列。值得注意的是，這隻有在保持堆不變的情況下才有效 - 除了其他亮點之外，還需要完美的平衡和有效的樹。

二叉樹不是堆的最高效表示形式; the Wikipedia article on binary heaps很好地解釋瞭如何使用數組來表示一個數組。 The article on Heapsort提到了一個有用的細節：如果使用數組表示，可以通過使用堆結束的空間來構建輸出數組，因爲堆始終平衡，並且刪除元素最終將釋放物理空間表示堆的最後一個單元格。