堆積 Heap · 資料結構 Data Structures

堆積

永遠能在一步內拿到最小值的樹，而且整棵樹就存在一個陣列裡。優先佇列就是它。

同一個堆積在記憶體裡的樣子：就是一個陣列。第 i 格的父節點在 (i−1)/2，子節點在 2i+1 和 2i+2。

4
0
9
1
7
2
15
3
12
4
10
5
20
6
18
7

正在比較交換／取出放入／到位

每個節點都不大於它的子節點，所以根節點一定是最小值。加入一個數，看它怎麼往上浮；或取出最小值，看補位的元素怎麼往下沉。

元素

樹高（層）

這次比較幾次

–

亮起來的是這一步執行的程式碼

1class MinHeap {
2  private a: number[] = [];
3 
4  push(value: number): void {
5    const a = this.a;
6    a.push(value);
7    let i = a.length - 1;
8    while (i > 0) {
9      const parent = (i - 1) >> 1;
10      if (a[i] >= a[parent]) break;
11      [a[i], a[parent]] = [a[parent], a[i]];
12      i = parent;
13    }
14  }
15 
16  pop(): number | undefined {
17    const a = this.a;
18    if (a.length === 0) return undefined;
19    const top = a[0];
20    const last = a.pop()!;
21    if (a.length === 0) return top;
22    a[0] = last;
23    let i = 0;
24    while (true) {
25      const left = 2 * i + 1, right = left + 1;
26      if (left >= a.length) break;
27      let smallest = i;
28      if (a[left] < a[smallest]) smallest = left;
29      if (right < a.length && a[right] < a[smallest]) smallest = right;
30      if (smallest === i) break;
31      [a[i], a[smallest]] = [a[smallest], a[i]];
32      i = smallest;
33    }
34    return top;
35  }
36 
37  peek(): number | undefined {
38    return this.a[0];
39  }
40}

模型假設與範圍

Big O 與實測步數以頁面列出的基本操作為單位；視覺化的快照、畫圖、程式高亮和輸出成本另計，不是執行時間 benchmark。

什麼時候用

資料不斷進出，而且每次都要「目前最小（或最大）的那一個」：排程、事件模擬、最短路徑。
從大量資料找前 k 名：只要維持一個大小為 k 的堆積。

和其他主題的關係

由這些組成: 動態陣列
被這些用到: 演算法 · 排序演算法 · 最短路徑演算法 · 最小生成樹演算法 · 考題：第 K 大與 Top-K 演算法 · 考題：合併 K 個排序串列演算法 · 考題：資料流的中位數演算法 · 掃描線與區間演算法 · 考題：會議室 II 系統設計 · 案例：動態牆系統設計 · 冪等與重試系統設計 · 案例：即時熱門排行
延伸閱讀: 二元搜尋樹

語言內建的版本

JavaScript／TypeScript 沒有內建的堆積或優先佇列。需要時用這頁上面那份實作（二十幾行），或套件；只要前幾名、資料又不多時，直接排序也行。

操作	寫法	成本
前 k 小（排序）	`[...nums].sort((x, y) => x - y).slice(0, 3)`	O(n log n)
最小值（掃一遍）	`Math.min(...nums)`	O(n)
插入有序陣列	`sorted.splice(at, 0, 4)`	O(n)
取出最小（有序陣列）	`sorted.shift()`	O(n)

const nums = [5, 1, 8, 3, 9, 2];
[...nums].sort((x, y) => x - y).slice(0, 3);   // → [1, 2, 3]
Math.min(...nums);                             // → 1
 
// A sorted array as a stand-in priority queue: fine for small n.
const sorted = [1, 3, 5, 8];
let at = sorted.findIndex((v) => v > 4);
if (at < 0) at = sorted.length;
sorted.splice(at, 0, 4);
sorted;                                        // → [1, 3, 4, 5, 8]
sorted.shift();                                // → 1
 
// Tasks by priority, ties in arrival order: sort is stable.
const tasks = [{ p: 2, name: "b" }, { p: 1, name: "a" }, { p: 2, name: "c" }];
tasks.sort((x, y) => x.p - y.p).map((t) => t.name);  // → ["a", "b", "c"]

每個 → 後面的結果都是實際執行這段程式碼驗證過的。

排序法每次都是 O(n log n)、有序陣列每次插入或取出都是 O(n)；資料一多、或要反覆「放進去、拿最小的」（例如 Dijkstra），就該用真正的堆積，每次 O(log n)。
Math.min(...nums) 會把整個陣列攤成參數，十幾萬個元素以上可能超過參數上限；大陣列用迴圈或 reduce。

出現在這些架構裡

時間與空間複雜度（Big O）

操作	平均	最差
加入隨機資料平均只往上浮一兩層；新的最小值才會一路浮到根	O(1)	O(log n)
取出最小值補位的是最底層的元素，幾乎一定要沉到底	O(log n)	O(log n)
看最小值	O(1)	O(1)
一次建好（heapify）	O(n)	O(n)
找任意一個值	O(n)	O(n)

空間：O(n)，就是一個陣列，不需要任何指標

Big O 實測：n 變大時步數怎麼長

數的是：比較次數（每種操作在該大小下做 1,000 次取平均）

	Big O	n = 1,000	n = 10,000	n = 100,000	n = 1,000,000	成長倍數：實測（理論）
加入新的最小值（最差）	O(log n)	9	13	16	19	×2.1 (×2.0)
加入隨機數（平均）	O(1)	2.6	2.3	2.3	2.3	×0.9 (×1.0)
取出最小值（平均）	O(log n)	17.7	24.5	31.3	37.8	×2.1 (×2.0)

n 變成一千倍，加入最小值和取出最小值的比較次數只變成兩倍左右（log n 從 10 變 20）；隨機加入則幾乎不變。

和其他做法比

	堆積：平均	堆積：最差	排序好的陣列	沒排序的陣列
加入	2.2	9	507.3	1
取出最小值	15.1	18	1	511.0

1,023 個隨機數全部加入再全部取出，數比較加搬動的次數。1,023 個節點的堆積正好 10 層，所以往上浮最多比較 9 次、往下沉每層 2 次。排序好的陣列取出很快但加入要搬一半；沒排序的陣列剛好相反。堆積兩邊都不差，這就是它當優先佇列的原因。

真實世界裡的它

作業系統的計時器與排程佇列、Python 的 heapq、Java 的 PriorityQueue。
Dijkstra 和 A* 用它挑下一個要探索的格子；heap sort 用它排序。

取捨與陷阱

只保證最上面是最小值，其他位置並沒有排序：要找任意一個值還是得整個掃一遍。
要調整某個元素的優先順序（decrease-key），得另外記住它在陣列中的位置。
一次把整個陣列變成堆積（heapify）只要 O(n)，比一個一個加入的 O(n log n) 快。

資料結構