Heapsort (堆積排序)


Sorting Problem


Input: A sequence of n numbers { \(a_0, a_1, ... , a_{n-1} \)}

Output: A permutation (reordering) { \(a'_0, a'_1, ... , a'_{n-1} \)} of the input sequence such that \( a'_0 \geq a'_1 \geq ... \geq a'_{n-1} \)

Heap Sort 概念


把 array 轉換成 max-heap,這是一種滿足 max-heap property 的 binary tree:對於除了 root 之外的每個 node i, A[parent(i)] \( \geq \) A[i]。

重複從 max-heap 取出數值最大的 node (把 root node 和 last node 交換,把交換後的 last node 移出 heap),並讓殘餘的 heap 維持 max-heap property。

C++ implementation




Performance Analysis


Worst case performance: \( O(n \log n) \)

Space complexity: \( O(1) \) auxiliary

延伸閱讀


[書籍] Introduction to Algorithms, 3rd. edition - Chap 6 Heapsort

[WiKi] 堆積排序

[WiKi] Heapsort

[WiKi] Heap (data structure)

系列文章



Insertion Sort (插入排序)

Merge Sort (合併排序)

Heapsort (堆積排序)