Visual C# 常用排序演算法（五）：堆積排序原理、堆定義與建堆過程圖解

基本思想

堆積排序屬樹形選擇排序，將陣列視為完全二元樹，利用父子節點關係選擇極值。

堆的定義

序列 K1, K2, ..., Kn 為堆，當且僅當滿足：
Ki ≤ K2i 且 Ki ≤ K2i+1 (對應小根堆，1 ≤ i ≤ ⌊n/2⌋)。

小根堆：根節點最小，任一非葉節點 ≤ 其子節點
大根堆：根節點最大，任一非葉節點 ≥ 其子節點

範例：10, 15, 56, 25, 30, 70 為小根堆，對應完全二元樹：

排序過程 (以大根堆為例)

1. 將無序區調整為大根堆
2. 交換堆頂 (最大值) 與無序區最後一個元素
3. 無序區縮減 1，有序區在陣列尾部擴大
4. 重複調整堆、交換、縮減，直到整個陣列有序

此過程與直接選擇排序相反：有序區從陣列尾部向前擴展。

建堆範例演示

關鍵字序列：42, 13, 91, 23, 24, 16, 05, 88

建堆過程圖解 (自上而下、自右而左調整非葉節點)：

下篇預告

完整 C# 程式碼實作與效能分析。