堆與堆排序 (Heap & Heap Sort)#
堆的定義#
堆是一種特殊的完全二元樹，滿足：
- 結構性質：完全二元樹（除最後一層外都填滿，最後一層靠左）
- 堆性質：每個節點 >= 或 <= 其子節點
| 類型 | 性質 | 堆頂 |
|---|---|---|
| 大頂堆 (Max Heap) | 父 >= 子 | 最大值 |
| 小頂堆 (Min Heap) | 父 <= 子 | 最小值 |
為什麼堆可以用一維陣列表示#
堆首先是一棵完全二元樹——這個「形狀」性質正是它能塞進陣列的關鍵。一般二元樹的形狀千變萬化，若硬要攤平成陣列，缺失的節點會在陣列中留下大量空洞，既浪費空間、索引也對不齊。而完全二元樹「除最後一層外都填滿、最後一層靠左」，等於保證了節點是連續、不留空洞的，於是可以一層一層、由左到右緊湊地寫進一維陣列。
只要把節點依「層序」放入陣列，父子關係就能純粹用索引算出來，完全不需要額外的指標：
| 樹的位置 | 陣列索引（從 0 起） |
|---|---|
| 根節點 | 0 |
| 第 2 層（左 ➡️ 右） | 1, 2 |
| 第 3 層（左 ➡️ 右） | 3, 4, 5, 6 |
對任一節點 i，三個鄰居都能直接算出：
| 關係 | 從 0 開始 | 從 1 開始 |
|---|---|---|
| 左子節點 | 2*i + 1 | 2*i |
| 右子節點 | 2*i + 2 | 2*i + 1 |
| 父節點 | (i-1) / 2 | i / 2 |
從索引 1 開始的公式（左子
2*i、右子2*i+1、父i/2）更簡潔，因此許多教科書與函式庫實作會刻意空出索引 0、從 1 開始放資料。下方「陣列存儲」一節即採此慣例。
陣列存儲#
完全二元樹特別適合用陣列存儲（從索引 1 開始）：
| 關係 | 公式 |
|---|---|
| 左子節點 | 2 * i |
| 右子節點 | 2 * i + 1 |
| 父節點 | i / 2 |
若從索引 0 開始：左子 =
2*i+1，右子 =2*i+2，父 =(i-1)/2
核心操作：堆化 (Heapify)#
上浮 (Sift Up) - 插入時使用#
fun siftUp(heap: MutableList<Int>, index: Int) {
var i = index
while (i > 1 && heap[i] > heap[i / 2]) {
val tmp = heap[i]; heap[i] = heap[i / 2]; heap[i / 2] = tmp
i /= 2
}
}下沉 (Sift Down) - 刪除堆頂時使用#
fun siftDown(heap: MutableList<Int>, n: Int, index: Int) {
var i = index
while (true) {
var maxPos = i
if (2 * i <= n && heap[2 * i] > heap[maxPos]) maxPos = 2 * i
if (2 * i + 1 <= n && heap[2 * i + 1] > heap[maxPos]) maxPos = 2 * i + 1
if (maxPos == i) break
val tmp = heap[i]; heap[i] = heap[maxPos]; heap[maxPos] = tmp
i = maxPos
}
}時間複雜度：O(log n)
兩個操作如何撐起整個堆#
上浮與下沉看似是兩段獨立程式碼，其實是堆對外兩個主要 API 的內部引擎：
| 對外操作 | 做法 | 底層用到 |
|---|---|---|
| 插入 (insert) | 把新元素放到陣列尾端，再上浮到正確位置 | sift up |
| 取出極值 (extract) | 把堆頂與尾端元素交換、刪掉尾端，再讓新堆頂下沉 | sift down |
換句話說，插入只是「放尾端 + 上浮」，取出極值只是「換尾端 + 下沉」；兩者都因為樹高是 O(log n)，所以本身也是 O(log n)。
以從 1 開始的大頂堆為例（沿用前面的 sift_up / sift_down，heap[0] 留空、size 為當前堆大小）：
// 插入：放尾端 + 上浮
fun insert(heap: MutableList<Int>, value: Int) {
heap.add(value) // 放到陣列尾端
siftUp(heap, heap.size - 1)
}
// 取出堆頂：換尾端 + 下沉
fun extractMax(heap: MutableList<Int>): Int {
val top = heap[1]
val last = heap.removeAt(heap.size - 1) // 移除尾端元素
if (heap.size > 1) { // 若還有元素，搬到堆頂再下沉
heap[1] = last
siftDown(heap, heap.size - 1, 1)
}
return top
}堆排序#
步驟#
flowchart LR
subgraph 階段一["階段 1：建堆"]
A1[無序陣列] --> A2[從最後一個<br/>非葉節點開始]
A2 --> A3[逐一下沉]
A3 --> A4[大頂堆完成]
end
subgraph 階段二["階段 2：排序"]
B1[取堆頂] --> B2[與末尾交換]
B2 --> B3[縮小堆範圍]
B3 --> B4[堆頂下沉]
B4 --> B5{堆為空?}
B5 -->|否| B1
B5 -->|是| B6[排序完成]
end
A4 --> B1
style A4 fill:#e8f5e9
style B6 fill:#e8f5e9- 建堆：將無序陣列建成大頂堆
- 排序：反覆取堆頂放到末尾，縮小堆範圍
堆排序程式碼
fun heapSort(arr: IntArray) {
val n = arr.size
// 原地堆排序採 0-indexed：node i 的子節點是 2i+1 與 2i+2
// （與前面 1-indexed 的 API 版 siftDown 不同，這裡用區域函式獨立處理）
fun siftDown(hi: Int, start: Int) {
var i = start
while (true) {
var maxPos = i
val left = 2 * i + 1
val right = 2 * i + 2
if (left <= hi && arr[left] > arr[maxPos]) maxPos = left
if (right <= hi && arr[right] > arr[maxPos]) maxPos = right
if (maxPos == i) break
val tmp = arr[i]; arr[i] = arr[maxPos]; arr[maxPos] = tmp
i = maxPos
}
}
// 建堆 - 從最後一個非葉節點開始下沉
for (i in n / 2 - 1 downTo 0) {
siftDown(n - 1, i)
}
// 排序 - 堆頂（最大值）與末尾交換，縮小堆再下沉
for (i in n - 1 downTo 1) {
val tmp = arr[0]; arr[0] = arr[i]; arr[i] = tmp
siftDown(i - 1, 0)
}
}複雜度#
- 建堆：
O(n)（不是O(n log n)！） - 排序：
O(n log n) - 空間：
O(1)（原地排序） - 穩定性：不穩定
堆排序 vs 快速排序：雖然都是
O(n log n)，但快排通常更快，因為：
- 堆排序資料訪問是跳躍的，對 CPU 快取不友好
- 建堆會打亂原有順序，增加交換次數
堆的應用#
優先佇列 (Priority Queue)#
import java.util.PriorityQueue
val pq = PriorityQueue<Int>() // 預設為小頂堆
pq.add(3) // 插入
pq.poll() // 取出最小值Top K 問題#
維護大小為 K 的小頂堆：
fun topK(nums: IntArray, k: Int): List<Int> {
val heap = PriorityQueue<Int>() // 小頂堆，堆頂即當前 K 個中的最小值
for (num in nums) {
if (heap.size < k) {
heap.add(num)
} else if (num > heap.peek()) {
heap.poll() // 移除最小值，換入更大的元素
heap.add(num)
}
}
return heap.toList()
}時間複雜度：O(n log k)
求中位數（動態資料）#
使用兩個堆：
- 大頂堆：存較小的一半
- 小頂堆：存較大的一半
- 中位數 = 大頂堆的堆頂
延伸應用：同樣方法可求任意百分位數，如 P99 響應時間。