Appearance
堆与优先队列
**堆（Heap）**是一种基于树的数据结构，满足两个核心性质：
- 结构性质：堆总是一棵完全二叉树（Complete Binary Tree）。除最底层外其他层都是满的，最底层节点靠左填充。
- 堆序性质：
- 最大堆（Max Heap）：任意节点的值 ≥ 其子节点的值，根节点总是最大值；
- 最小堆（Min Heap）：任意节点的值 ≤ 其子节点的值，根节点总是最小值。
尽管堆逻辑上是树，但在物理存储上使用数组（std::vector），通过索引直接定位父子节点：
text
父节点 i：左孩子 2*i + 1，右孩子 2*i + 2插入时将新元素放到末尾并向上调整（sift up / shift up）；删除堆顶时将末尾元素移到堆顶并向下调整（sift down / shift down）。
对下标 i > 0，父节点是 (i - 1) / 2，孩子是 2 * i + 1 和 2 * i + 2。数组保持的是层序位置；最大/最小关系只约束父子，不保证兄弟或整段数组有序。
首选：std::priority_queue
默认是大顶堆，用小顶堆需要指定 std::greater：
cpp
#include <functional>
#include <queue>
#include <vector>
std::priority_queue<int> max_heap;
max_heap.push(3);
max_heap.push(1);
max_heap.push(5);
int largest = max_heap.top(); // 5
max_heap.pop(); // 删除 5，O(log n)
std::priority_queue<int, std::vector<int>, std::greater<int>> min_heap;
min_heap.push(3);
min_heap.push(1);
min_heap.push(5);
int smallest = min_heap.top(); // 1自定义元素时，比较器表达 "a 的优先级是否低于 b"：
cpp
#include <queue>
#include <string>
#include <vector>
struct Task {
int priority; // 越小优先级越高
std::string name;
};
struct HigherPriority {
bool operator()(const Task& a, const Task& b) const {
return a.priority > b.priority; // a 更靠后，形成小顶堆
}
};
std::priority_queue<Task, std::vector<Task>, HigherPriority> tasks;
tasks.push({10, "normal"});
tasks.push({1, "urgent"});
Task next = tasks.top(); // {1, "urgent"}堆算法：复用 vector
当需要查看或操作底层数组时，使用 <algorithm> 的堆算法：
cpp
#include <algorithm>
#include <vector>
std::vector<int> values{4, 1, 7, 3};
std::make_heap(values.begin(), values.end()); // 建大顶堆，整体 O(n)
values.push_back(9);
std::push_heap(values.begin(), values.end()); // 新末尾元素上滤，O(log n)
std::pop_heap(values.begin(), values.end()); // 最大值移到末尾，O(log n)
int largest = values.back();
values.pop_back();std::pop_heap 只将堆顶交换到区间末尾，不会缩短 vector，还需要调用 pop_back()。
操作复杂度与 heapify 为什么是 O(n)
| 操作 | 时间 | 说明 |
|---|---|---|
top | O(1) | 直接读取下标 0 |
push | O(log n) | 新元素从末尾上浮，最多走树高 |
pop | O(log n) | 尾元素移到堆顶后下沉 |
| 已知下标的更新 / 删除 | O(log n) | 上浮或下沉其一即可 |
| 按值查找 | O(n) | 堆不提供按任意 key 的有序定位 |
自底向上 heapify | O(n) | 大量节点靠近叶子，下沉距离很短 |
| 空间 | O(n) | 连续数组 |
从空堆逐个插入 n 个元素是 O(n log n)，但对已有无序数组，从最后一个非叶子节点开始依次下沉的 Floyd 建堆是 O(n)：节点数随高度指数下降，总代价满足 Σ (n / 2^(h+1)) · h = O(n)。
手写最大堆 MaxHeap
以下实现固定 int 类型，聚焦上浮（shift up）和下沉（shift down）的核心逻辑：
cpp
#include <algorithm>
#include <cstddef>
#include <stdexcept>
#include <vector>
class MaxHeap {
private:
// 完全二叉树按层序连续存储；下标 0 始终是堆顶。
std::vector<int> heap;
// 0-based 索引关系。parent(i) 只在 i > 0 时调用，避免无符号下溢。
static std::size_t parent(std::size_t i) { return (i - 1) / 2; }
static std::size_t left(std::size_t i) { return 2 * i + 1; }
static std::size_t right(std::size_t i) { return 2 * i + 2; }
// 插入只可能破坏“新节点到根”这条路径上的堆序。
// 若当前节点大于父节点，就交换并继续向上；最多上浮树高 O(log n)。
void shiftUp(std::size_t i) {
while (i > 0) {
const std::size_t p = parent(i);
if (heap[i] <= heap[p]) {
break; // 当前节点不大于父节点，堆序已经恢复。
}
std::swap(heap[i], heap[p]);
i = p;
}
}
// 删除堆顶后，只可能破坏“根到某个叶子”路径上的堆序。
// 每次从当前节点和两个孩子中选最大者；若孩子更大，就交换后继续下沉。
void shiftDown(std::size_t i) {
std::size_t maxIndex = i;
const std::size_t l = left(i);
const std::size_t r = right(i);
const std::size_t n = heap.size();
// 先与左孩子比较，再用当前最大候选与右孩子比较。
if (l < n && heap[l] > heap[maxIndex]) {
maxIndex = l;
}
if (r < n && heap[r] > heap[maxIndex]) {
maxIndex = r;
}
if (maxIndex == i) {
return; // 当前节点已经不小于两个孩子，无需继续下沉。
}
std::swap(heap[i], heap[maxIndex]);
shiftDown(maxIndex); // 递归深度最多为树高 O(log n)。
}
public:
void push(int val) {
// 放在数组末尾可以继续保持完全二叉树的结构性质。
heap.push_back(val);
// 只有新节点与祖先之间可能违反最大堆性质。
shiftUp(heap.size() - 1);
}
void pop() {
// 此接口约定：空堆执行 pop 是无操作；也可以改为抛出异常。
if (heap.empty()) return;
// 用最后一个节点覆盖堆顶，再删除数组末尾，保持完全二叉树形状。
heap[0] = heap.back();
heap.pop_back();
// 新堆顶可能小于孩子，需要向下恢复最大堆性质。
if (!heap.empty()) {
shiftDown(0);
}
}
int top() const {
if (heap.empty()) {
throw std::runtime_error("Heap is empty");
}
return heap[0]; // 堆顶位于下标 0，读取为 O(1)。
}
std::size_t size() const { return heap.size(); }
bool empty() const { return heap.empty(); }
};使用示例：
cpp
MaxHeap h;
h.push(10);
h.push(20);
h.push(5);
h.push(30);
h.push(15);
// top() == 30
h.pop(); // 删除 30
// top() == 20泛型版本
如果需要支持自定义类型和比较器，只需将 int 替换为模板参数，并接受一个比较器对象（默认为 std::greater<T> 形成大顶堆，传入 std::less<T> 形成小顶堆），下沉时按比较器选择孩子。
原地堆化（Heapify）：把无序数组建成堆
将无序数组原地转换为堆，有两种方法：
方法一：自下而上（Bottom-up）— 推荐，O(n)
从最后一个非叶子节点开始向前遍历到根，对每个节点执行 shiftDown（下沉）。叶子节点本身已是合法堆；处理非叶子节点时，其子树已是堆，下沉后当前子树完整成堆。
cpp
void buildHeap(std::vector<int>& nums) {
int n = nums.size();
for (int i = n / 2 - 1; i >= 0; --i) {
shiftDown(nums, n, i);
}
}最后一个非叶子节点的索引为 n / 2 - 1。shiftDown 接受 n 参数以限定堆范围（堆排序时有用）。
时间复杂度 O(n)：虽然单次 shiftDown 是 O(log n)，但大部分节点靠近叶子，下沉路径很短。节点数随高度指数下降，总和满足 Σ (n / 2^(h+1)) · h = O(n)。
方法二：自上而下（Top-down）— O(n log n)
从索引 1 开始向后遍历，对每个元素执行 shiftUp（上浮），模拟逐个插入：
cpp
void buildHeapSlow(std::vector<int>& nums) {
for (int i = 1; i < nums.size(); ++i) {
int j = i;
while (j > 0 && nums[j] > nums[(j - 1) / 2]) {
std::swap(nums[j], nums[(j - 1) / 2]);
j = (j - 1) / 2;
}
}
}叶子节点（数量最多）上浮路径最长，因此总复杂度为 O(n log n)。
对比
| 方法 | 操作 | 遍历方向 | 时间复杂度 | 典型场景 |
|---|---|---|---|---|
| 自下而上 | shiftDown | 从后向前（非叶→根） | O(n) | std::make_heap、建堆 |
| 自上而下 | shiftUp | 从前向后（第 2 个→尾） | O(n log n) | 逐个插入新元素 |
C++
std::make_heap使用的是自下而上的 O(n) 算法。
priority update、任意删除与索引堆
标准 priority_queue 和上面的裸堆都能高效维护堆顶，但不知道某个业务 key 位于哪里。要支持"取消某个定时器"或"按任务 id 提升优先级"，常见方案是：
- 延迟删除：新版本入堆，旧版本保留；弹出时检查版本号 / 取消标记；
- 索引堆：额外维护
key → heap_index哈希表；每次交换元素时同步更新下标； - 改用平衡树：如果需要按 key 查找、范围查询和最值，可用
std::set/std::map，代价是每项操作 O(log n)。
延迟删除实现简单但堆可能积累失效元素，需要在弹出时清理或定期重建。索引堆能把已知 key 的更新和删除维持在 O(log n)，但重点是"每次交换都更新索引"，否则下标会立刻失效。
常见应用
| 场景 | 堆顶含义 |
|---|---|
| Top K | 维护大小为 K 的小顶堆，堆顶是当前第 K 大候选 |
| 定时器 | 小顶堆按触发时间排序，堆顶是最近到期任务 |
| 任务调度 | 堆顶是最高优先级任务 |
| 匹配队列 | 按价格、时间或优先级选取下一候选 |
注意堆只保证堆顶最优，内部元素不是完全排序的，不能当作有序容器遍历。
易错点
std::priority_queue::pop()不返回元素，需要先top()再pop()；std::pop_heap不会缩短容器，之后还要pop_back()；- 堆排序的输出是有序的，但堆的底层数组本身不是完整排序结果；
- 用
size_t倒序建堆时，不能写for (size_t i = n / 2 - 1; i >= 0; --i)，会下溢并无限循环。