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 (堆積排序)
