最紧急者优先的结构
想象一间医院急诊室。病人不是按到达顺序就诊（那是队列），也不是按名字（那是有序树）——而是按*危急程度*。最重的先看，不论他什么时候进来。对应的抽象工具是[[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|堆排序]]，它是把堆变成一个排序器，就地完成，不需要额外的数组。同一种结构，既能跑你的优先队列，也能给你的数据排序。