树与层次结构
堆
堆是一种为一件事而调校的二叉树：随时、即刻地知道最小（或最大）的元素。它不是查找树——它给出的承诺弱得多，即堆性质：每个父节点都小于等于它的子节点（小顶堆），或大于等于它的子节点（大顶堆）。对左右兄弟之间的大小则只字不提，所以堆只是部分有序——刚好够把那个极值钉在根上。
两个设计选择让它很快。其一，堆是一棵完全二叉树：除可能的最后一层外，每一层都填满，而最后一层从左到右依次填入。这种完美形状意味着树高始终约为 log n，绝不会退化。其二，正因为形状如此规整，你根本不需要指针——把堆直接存进一个普通数组，下标 i 的两个子节点落在 2i+1 和 2i+2，父节点在 (i-1)/2。整棵树都隐含在这套下标算术里。
插入时把新元素放到末尾，让它一路向上冒泡、越过每个比它大的父节点；删除堆顶时把最后一个元素换上来，再让它向下沉到合适的层。每次修复都只走一条从根到叶的路径，所以插入与取最小/取最大都是 O(log n)，而查看堆顶是 O(1)，因为它就是数组的第一个槽位。这套组合正是优先队列所需，而反复读出元素则是堆排序的核心。
// min-heap stored in vector<int> h
void push(vector<int>& h, int x) {
h.push_back(x);
int i = h.size() - 1;
while (i > 0 && h[(i - 1) / 2] > h[i]) {
swap(h[i], h[(i - 1) / 2]); // sift up
i = (i - 1) / 2;
}
}数组实现的堆：插入先追加再上浮，是 O(log n) 操作。
堆只能快速找到那一个最小或最大值——它无法以 O(log n) 查找任意的键；那是二叉搜索树的活儿。
又称
另见