堆排序（heap sort）介紹

 堆排序（heap sort）是什麼

透過堆（樹狀結構）做排序，適用有效找前K名最大值。排序過程：

1. 建堆：將數列做廣域優先走訪逐步建立樹，經由葉節點往上比較逐步建最大/小堆。

2. 排序：將樹根與最後一個葉節點交換後，最後一個葉節點變成已排好，將未排好的樹結構再次變成堆。如此透過不斷將樹根與最後一個葉節點交換，以完成一個排序好的數列。

舉例

有一個數列[5, 3, 8, 4, 1, 2]用堆排序排成由小至大數列。

1. 建堆

由左至右掃描數列，用廣度優先放置掃到元素至一棵二元樹。

將樹建最大堆。

2. 排序，底線節點為已排序好的節點

時間複雜度

建二元樹（遍歷數列）需要O(n)時間複雜度，每次從堆中取最大元素並做堆化過程需O(logn)，要做n次操作。故時間複雜度為O(nlogn)。

空間複雜度

屬原地排序演算法，需常數空間存輔助變數，故空間複雜度為O(1)。

堆排序與快速排序比較

1. Heap sort 內存（用陣列實現的二元樹）訪問不連續效率低。
2. 堆調整涉及多次筆記與交換。

所以堆排序的開銷（overhead）比快速排序高。