最緊急者優先的結構
想像一間醫院急診室。病人不是按到達順序就診（那是佇列），也不是按名字（那是有序樹）——而是按*危急程度*。最重的先看，不論他什麼時候進來。對應的抽象工具是[[priority-queue|優先佇列]]：你把帶優先級的元素丟進去，每次要一個，就拿到當前可用的最高優先級那一個。讓這件事變快的資料結構，就是[[heap|堆積]]。
堆積是一棵帶兩個承諾的二元樹。第一，形狀：它是一棵*完全*二元樹——除最後一層外每一層都滿，而最後一層從左到右填充、不留空隙。第二，堆積性質：每個父節點都 ≥ 它的兩個孩子（*大頂堆*）——或者 ≤，那是*小頂堆*。注意這比 BST 弱：沒有左右之分的排序，只有「父勝子」的關係。這條更弱的規則就是代價交換：堆積讓你瞬間拿到那唯一的頂端元素，卻不給你一個完全有序的視圖。
A max-heap (every parent >= its children):
(50)
/ \
(30) (40)
/ \ /
(10) (20) (35)
top is always the maximum (50).
NOTE: it is NOT left<right -- 30's children 10,20 are fine,
but a heap makes no promise about order across siblings.一棵沒有指針的樹：陣列把戲
這裡是本篇最美的想法。因為堆積是*完全*的（沒有空隙），你可以把它一層一層、從上到下、從左到右地倒進一個扁平陣列裡——於是父子鏈接變成純粹的算術。沒有 `Node`，沒有 `left`/`right` 指針，沒有 `new`。對下標為 `i` 的節點：
tree: (50) array (index):
/ \ 0:50 1:30 2:40 3:10 4:20 5:35
(30) (40)
/ \ / for node at index i:
(10)(20)(35) left child = 2*i + 1
right child = 2*i + 2
parent = (i - 1) / 2
index 1 (=30): left=2*1+1=3 (10), right=2*1+2=4 (20). yes!壓入與彈出：上浮與下沉
兩個操作讓堆積保持誠實。壓入（push）：把新值放到陣列末尾（保持完全形狀），然後讓它*上浮*——只要它比父節點大，就和父節點交換。每次交換它最多爬一層，所以會在樹高之內停下。彈出（pop）最大值：取走根（那就是答案），把最後一個元素挪到根上以保持形狀，然後讓它*下沉*——不斷與它較大的那個孩子交換，直到堆積性質重新成立。
- top — 讀根，即 `heap[0]`。什麼都不動。O(1)。
- push — 追加到末尾，然後只要比父節點大就上浮。每層至多一次交換：O(log n)。
- pop — 保存根，把最後一個元素移到最前，再讓它下沉。同樣每層一次交換：O(log n)。
std::priority_queue，以及一次免費的排序
你同樣很少親手寫堆積——C++ 給了你 `std::priority_queue`，開箱即用的大頂堆，帶著 `push`、`top`、`pop`，與前面描述的一模一樣。（想要小頂堆，讓*最小*的先冒出來？傳一個 `std::greater<>` 比較器。）
#include <queue> std::priority_queue<int> pq; // a max-heap pq.push(30); pq.push(50); pq.push(40); std::cout << pq.top(); // 50 -- the largest, O(1) pq.pop(); // remove 50, O(log n) std::cout << pq.top(); // 40 -- next largest // a min-heap (smallest on top): // std::priority_queue<int, std::vector<int>, std::greater<int>> minpq;
再來一個對排序那一級的可愛回響：如果你把全部 n 個元素都壓進一個堆，再一個一個彈出，它們就按有序出來。n 次彈出，每次 O(log n)，合計 O(n log n)——和合併排序同一檔。這個演算法就是 [[heapsort|堆積排序]]，它是把堆變成一個排序器，就地完成，不需要額外的陣列。同一種結構，既能跑你的優先佇列，也能給你的資料排序。