堆（heap）解决的不是「把所有元素排好」，而是一个更克制、也更常见的承诺：在持续插入、删除中，始终用很低的代价拿到当前最优元素。最短路每次扩展距离最小的点、事件系统每次取最早到期的任务、流式数据保留最大的 kk 个数、多路归并选择各路的最小头部，都是同一件事：只维护堆顶，而不维护全局次序。

这使堆成为 BFS 的队列模型、图论 的 Dijkstra/Prim 模型与 排序 的选择模型之间的重要连接。本文从数组表示与不变量出发，手写最小堆，再落到 std::priority_queue、TopK、归并、在线中位数和会议室调度。

为什么需要堆：只维护“冠军”

设有 nn 个待选元素。若每次在线性数组中扫描最小值，取一次要 O(n)O(n)；若将数组全排好，第一次取最小值容易，但每次新插入仍可能要移动 O(n)O(n) 个元素。堆只保证根是最优元素，每次插入或删除只修复一条从叶到根、或从根到叶的路径，因此二者都是 O(log⁡n)O(\log n)，查看堆顶为 O(1)O(1)。

最小堆的核心不变量是：对每个非根节点 ii，都有

a[parent⁡(i)]≤a[i].a[\operatorname{parent}(i)] \le a[i].

它只推出祖先不大于后代；同层节点、不同子树的节点完全可能乱序。例如 [1, 4, 2, 9, 7, 3] 是合法最小堆，但 4 > 2。把堆误当作已排序数组，是所有堆题中最常见的思维错误。

堆适合以下问题：

  • 数据不断抵达，随时要当前最小/最大值；
  • 每轮只关心候选集里的最佳者，如 Dijkstra 的最短暂定距离；
  • 只保留 kk 个候选，如第 kk 大、TopK 高频元素；
  • 有 kk 路已排序输入，每轮取最小头部；
  • 两个集合各维护边界值，如动态中位数。

若需要按任意键查找、删除某个指定元素，普通堆没有位置索引，不能替代平衡树或哈希表；若需要完整有序输出，则排序往往更直接。

完全二叉树为何能压进数组

二叉堆是一棵完全二叉树：除最后一层外每层填满，最后一层从左到右连续填入。没有空洞意味着按层序编号后，节点天然连续，指针和空孩子都不需要存。令根下标为 0，则节点关系恰由算术给出：

parent⁡(i)=⌊i−12⌋,left⁡(i)=2i+1,right⁡(i)=2i+2.\operatorname{parent}(i)=\left\lfloor\frac{i-1}{2}\right\rfloor,\quad \operatorname{left}(i)=2i+1,\quad \operatorname{right}(i)=2i+2.

parent(0) 没有定义，调用前必须确认 i > 0；孩子下标必须小于 n 才存在。高度为 ⌊log⁡2n⌋\lfloor\log_2 n\rfloor，这正是上滤、下滤的最长路径长度。

0 下标数组中的完全二叉树映射；每个节点的父、左孩子、右孩子下标都由固定公式获得

下面的程序把公式直接打印出来。注意 parent 对根返回 std::nullopt，不要让无符号下标在 i - 1 处下溢。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include <iostream>
#include <optional>
#include <vector>

std::optional<int> parent(int index) {
  if (index == 0) return std::nullopt;
  return (index - 1) / 2;
}

int left(int index) {
  return index * 2 + 1;
}

int right(int index) {
  return index * 2 + 2;
}

int main() {
  const std::vector<int> heap{1, 4, 2, 9, 7, 3};
  for (int i = 0; i < static_cast<int>(heap.size()); ++i) {
    std::cout << "i=" << i << ", parent=";
    if (const auto p = parent(i); p.has_value()) {
      std::cout << *p;
    } else {
      std::cout << "none";
    }
    std::cout << ", left=" << left(i)
              << ", right=" << right(i) << '\n';
  }
}

叶子与最后一个非叶节点

下标大于等于 ⌊n/2⌋\lfloor n/2\rfloor 的节点没有左孩子，因而全是叶子；反之，最后一个可能有孩子的节点为

⌊n2⌋−1.\left\lfloor\frac{n}{2}\right\rfloor - 1.

这条边界是自底向上建堆的起点。n == 0 时它会算成 -1，因此 C++ 循环必须用有符号 int，或先显式处理空数组；把 n / 2 - 1 放进 size_t 是经典下溢 bug。

手写最小堆：两种局部修复

对最小堆，任何破坏只会沿一条路径传播：

  • siftUp（上滤）：新元素先放数组尾部；若它小于父亲，就交换并继续向上。它修复“叶子太小”。
  • siftDown（下滤）：删除根后，把最后元素填到根；在两个孩子中选择较小者交换并继续向下。它修复“根太大”。

每一步只需要比较常数个元素。更关键的是，siftDown 必须先选较小的孩子：若先和左孩子交换而右孩子更小，交换后根仍可能大于右孩子，最小堆不变量立即失败。

一个带空堆边界的最小堆模板

以下 MinHeap 以 std::vector<int> 持有元素，所有公有查询都对空堆给出可检查的结果：top() 与 pop() 返回 std::optional<int>。题库接口若承诺操作合法，也可以改为返回 int；工程接口不应在空堆时读取 data_[0]。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
#include <iostream>
#include <optional>
#include <utility>
#include <vector>

class MinHeap {
 public:
  [[nodiscard]] bool empty() const {
    return data_.empty();
  }

  [[nodiscard]] int size() const {
    return static_cast<int>(data_.size());
  }

  [[nodiscard]] std::optional<int> top() const {
    if (data_.empty()) return std::nullopt;
    return data_.front();
  }

  void push(int value) {
    data_.push_back(value);
    siftUp(static_cast<int>(data_.size()) - 1);
  }

  std::optional<int> pop() {
    if (data_.empty()) return std::nullopt;
    const int answer = data_.front();
    data_.front() = data_.back();
    data_.pop_back();
    if (!data_.empty()) siftDown(0);
    return answer;
  }

 private:
  static int parent(int index) {
    return (index - 1) / 2;
  }

  static int left(int index) {
    return index * 2 + 1;
  }

  static int right(int index) {
    return index * 2 + 2;
  }

  void siftUp(int index) {
    while (index > 0) {
      const int p = parent(index);
      if (data_[p] <= data_[index]) break;
      std::swap(data_[p], data_[index]);
      index = p;
    }
  }

  void siftDown(int index) {
    const int n = static_cast<int>(data_.size());
    while (left(index) < n) {
      int child = left(index);
      const int r = right(index);
      if (r < n && data_[r] < data_[child]) child = r;
      if (data_[index] <= data_[child]) break;
      std::swap(data_[index], data_[child]);
      index = child;
    }
  }

  std::vector<int> data_;
};

int main() {
  MinHeap heap;
  std::cout << heap.empty() << '\n';
  std::cout << heap.pop().has_value() << '\n';
  for (int x : {5, 1, 4, 1, 3}) heap.push(x);
  while (const auto value = heap.pop()) {
    std::cout << *value << ' ';
  }
  std::cout << '\n';
}

pop() 中即使只剩一个元素，先把 front() 赋为 back() 也安全；紧随其后的 pop_back() 让数组变空，因而不会下滤。重复值也安全：不变量是 <=，不必为了相等元素继续无意义交换。

操作的正确性视角

插入前，除数组末尾之外所有位置都是合法堆。新增元素的孩子不存在，所以它最多违反与父亲的一条边；每次交换后，原父亲落到更大的位置，和它的孩子仍满足关系，违例只可能继续向上。删除根同理：最后元素替到根后，除根外全堆合法；选较小孩子交换保证新父亲不大于另一孩子，违例只可能继续向下。

操作修改的位置修复方向时间额外空间
top无无O(1)O(1)O(1)O(1)
push末尾向根上滤O(log⁡n)O(\log n)O(1)O(1)
pop根与末尾向叶下滤O(log⁡n)O(\log n)O(1)O(1)
heapify全数组多次下滤O(n)O(n)O(1)O(1)

自底向上建堆：为什么不是 O(nlog⁡n)O(n\log n)

将 nn 个元素逐个 push 当然能建堆，最坏为 O(nlog⁡n)O(n\log n)。更快的方法是把原数组视为完全二叉树，从最后一个非叶节点 n / 2 - 1 一直下滤到根。处理一个节点前，它的两个子树已经是合法堆，所以一次下滤即可让整个子树合法。

Floyd 自底向上建堆从最后一个非叶节点开始；每次下滤都建立一个更高子树的不变量，最后根覆盖整棵树

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#include <algorithm>
#include <iostream>
#include <utility>
#include <vector>

void siftDown(std::vector<int>& values, int root, int n) {
  while (root * 2 + 1 < n) {
    int child = root * 2 + 1;
    const int right = child + 1;
    if (right < n && values[right] > values[child]) {
      child = right;
    }
    if (values[root] >= values[child]) break;
    std::swap(values[root], values[child]);
    root = child;
  }
}

void buildMaxHeap(std::vector<int>& values) {
  const int n = static_cast<int>(values.size());
  for (int i = n / 2 - 1; i >= 0; --i) {
    siftDown(values, i, n);
  }
}

int main() {
  std::vector<int> values{3, 1, 6, 5, 2, 4};
  buildMaxHeap(values);
  for (int x : values) std::cout << x << ' ';
  std::cout << '\n';
  std::cout << std::is_heap(values.begin(), values.end()) << '\n';
}

这里特意构造的是最大堆，以便稍后堆排序复用。对最小堆只需翻转比较方向。std::is_heap 只作为示例展示标准库的判定接口；算法本身不依赖它。

高度求和的直觉

表面上有约 n/2n/2 个内部节点、一次下滤最坏 O(log⁡n)O(\log n)，粗糙上界得到 O(nlog⁡n)O(n\log n)，却忽略了绝大多数节点很矮。高度为 hh 的节点至多约 n/2h+1n/2^{h+1} 个，建堆总工作量被下式控制：

∑h=0⌊log⁡n⌋n2h+1⋅O(h)=O(n)∑h≥0h2h+1=O(n).\sum_{h=0}^{\lfloor\log n\rfloor} \frac{n}{2^{h+1}}\cdot O(h) = O(n)\sum_{h\ge0}\frac{h}{2^{h+1}} = O(n).

叶子数量最多但高度为 0，几乎不用工作；能下沉很多层的根极少。这是分层数据结构分析里很值得记住的模式：不能只拿“单次最坏成本”乘“元素个数”。

std::priority_queue：比较器方向先想清楚

C++ 的 std::priority_queue<T, Container, Compare> 默认是最大堆：top() 给出按 Compare 意义上的最大优先级元素。默认 std::less<T> 令数值大的元素在顶；传入 std::greater<T> 则令数值小的元素在顶。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#include <functional>
#include <iostream>
#include <queue>
#include <vector>

struct Job {
  int deadline;
  int id;
};

struct EarlierDeadline {
  bool operator()(const Job& a, const Job& b) const {
    return a.deadline > b.deadline;
  }
};

int main() {
  std::priority_queue<int> maxHeap;
  using MinHeap = std::priority_queue<
      int, std::vector<int>, std::greater<int>>;
  MinHeap minHeap;
  for (int x : {4, 1, 7}) {
    maxHeap.push(x);
    minHeap.push(x);
  }
  std::cout << maxHeap.top() << ' ' << minHeap.top() << '\n';

  std::priority_queue<Job, std::vector<Job>, EarlierDeadline> jobs;
  jobs.push({5, 42});
  jobs.push({2, 7});
  std::cout << jobs.top().deadline << ' ' << jobs.top().id << '\n';
}

自定义比较器最稳妥的读法是：comp(a, b) == true 表示 a 的优先级低于 b，因此 b 更应接近堆顶。上述 a.deadline > b.deadline 意味着截止时间晚的任务优先级更低，故最早截止任务在顶。它看起来与 std::sort 的“true 表示 a 排前面”相反，正是错用比较器的根源。

目标堆顶priority_queue 写法自定义 comp(a,b) 应返回 true 的条件
最大数std::priority_queue<int>a.key < b.key
最小数..., std::greater<int>a.key > b.key
最早截止任务EarlierDeadlinea.deadline > b.deadline
最大频率但键小优先自定义freq 小，或频率同而键大

priority_queue 没有迭代排序接口，也不支持修改堆内元素后自动重排。若元素的排序键被外部修改，堆不变量立刻失效；正确办法是弹出旧条目、推入新条目，或采用“多版本条目 + 弹出时跳过陈旧版本”的模式。这正是 图论 中堆优化 Dijkstra 的写法。

堆排序：原地、O(nlog⁡n)O(n\log n)、但不稳定

堆排序先把数组建成最大堆，再反复把根（当前最大值）和有效区间末尾交换，并对缩短后的区间下滤。这样最大值从右向左落位，最终数组升序。它只用常数额外空间，最坏和平均时间都为 O(nlog⁡n)O(n\log n)，没有快速排序的最坏 O(n2)O(n^2) 风险。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#include <algorithm>
#include <iostream>
#include <utility>
#include <vector>

void siftDown(std::vector<int>& a, int root, int limit) {
  while (root * 2 + 1 < limit) {
    int child = root * 2 + 1;
    if (child + 1 < limit && a[child] < a[child + 1]) {
      ++child;
    }
    if (a[root] >= a[child]) break;
    std::swap(a[root], a[child]);
    root = child;
  }
}

void heapSort(std::vector<int>& a) {
  const int n = static_cast<int>(a.size());
  for (int i = n / 2 - 1; i >= 0; --i) siftDown(a, i, n);
  for (int last = n - 1; last > 0; --last) {
    std::swap(a[0], a[last]);
    siftDown(a, 0, last);
  }
}

int main() {
  std::vector<int> values{5, 1, 5, 2, 0};
  heapSort(values);
  for (int x : values) std::cout << x << ' ';
  std::cout << '\n';
}

堆排序不稳定：相等键的元素可能在“根与末尾交换”时跨越彼此。若记录携带同一时间戳下的原始顺序，或排序稳定性是业务语义，优先考虑稳定归并排序或 std::stable_sort。另一个现实选择是 std::sort：其 introsort 通常更快，且具备最坏 O(nlog⁡n)O(n\log n) 保证；手写堆排序更多用于理解与严格的原地最坏界场景。

TopK：维护答案边界，而非维护全体

TopK 的关键不是“用堆”，而是让堆顶成为当前答案里最容易被淘汰的元素。求第 kk 大时保留最大的 kk 个数，应使用容量为 kk 的最小堆；堆顶是这 kk 个数中最小的，即第 kk 大候选。新数若不大于堆顶，必定无缘答案；更大则替换堆顶。

LeetCode 215：数组中的第 K 个最大元素

以下实现明确处理 k == 0、k > n 和空输入：这些情况下不存在第 kk 大，返回 std::nullopt。不要在 k == 0 时仍调用 top() 或 pop()，容量为零的堆永远不能保存边界。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
#include <functional>
#include <iostream>
#include <optional>
#include <queue>
#include <vector>

std::optional<int> findKthLargest(
    const std::vector<int>& values, int k) {
  if (k <= 0 || k > static_cast<int>(values.size())) {
    return std::nullopt;
  }

  using MinHeap = std::priority_queue<
      int, std::vector<int>, std::greater<int>>;
  MinHeap heap;
  for (int value : values) {
    heap.push(value);
    if (static_cast<int>(heap.size()) > k) heap.pop();
  }
  return heap.top();
}

int main() {
  const std::vector<int> values{3, 2, 1, 5, 6, 4};
  if (const auto answer = findKthLargest(values, 2)) {
    std::cout << *answer << '\n';
  }
  std::cout << findKthLargest(values, 0).has_value() << '\n';
}

时间为 O(nlog⁡k)O(n\log k)，空间为 O(k)O(k)。当 kk 接近 nn，直接建最大堆并弹出 k−1k-1 次是 O(n+klog⁡n)O(n+k\log n)；当只要单个第 kk 大，快速选择的期望 O(n)O(n) 也很有竞争力。固定大小堆的优势是在线：元素无需一次性到齐，答案随流更新。

TopK 高频：堆里放“频率”，不是原元素

若先用哈希表计数，再输出频率最大的 kk 个键，同样维护容量 kk 的小根堆；最小频率位于堆顶。比较器必须规定频率相等时的规则，避免答案因容器内部布局而难以复现。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
#include <functional>
#include <iostream>
#include <queue>
#include <unordered_map>
#include <utility>
#include <vector>

using Entry = std::pair<int, int>;  // (频率, 数值)

std::vector<int> topKFrequent(
    const std::vector<int>& values, int k) {
  if (k <= 0) return {};
  std::unordered_map<int, int> count;
  for (int value : values) ++count[value];

  using MinHeap = std::priority_queue<
      Entry, std::vector<Entry>, std::greater<Entry>>;
  MinHeap heap;
  for (const auto& [value, frequency] : count) {
    heap.push({frequency, value});
    if (static_cast<int>(heap.size()) > k) heap.pop();
  }

  std::vector<int> answer(heap.size());
  for (int i = static_cast<int>(answer.size()) - 1; i >= 0; --i) {
    answer[i] = heap.top().second;
    heap.pop();
  }
  return answer;
}

int main() {
  const auto answer = topKFrequent({1, 1, 1, 2, 2, 3}, 2);
  for (int value : answer) std::cout << value << ' ';
  std::cout << '\n';
}

这里 std::pair 的字典序使频率相同时值较小的条目先弹出；这意味着若候选数超过容量，数值较小者更容易被淘汰。题目未要求并列规则时可接受；要求字典序最小答案时，应把并列规则明确写进比较器和最终排序。

多路归并：堆里永远只有各路头部

给定 kk 个各自升序的链表（LeetCode 23），所有未消费元素中最小者一定在某条链表的头部。故堆无需装入全部 NN 个节点，只装至多 kk 个头节点：弹出最小节点，把它的后继推入。堆顶选择下一项，链表自身提供同一路的后继。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
#include <functional>
#include <iostream>
#include <queue>
#include <vector>

struct ListNode {
  int val;
  ListNode* next;
  explicit ListNode(int value) : val(value), next(nullptr) {}
};

struct NodeGreater {
  bool operator()(const ListNode* a, const ListNode* b) const {
    return a->val > b->val;
  }
};

ListNode* mergeKLists(std::vector<ListNode*> lists) {
  using NodeHeap = std::priority_queue<
      ListNode*, std::vector<ListNode*>, NodeGreater>;
  NodeHeap heap;
  for (ListNode* head : lists) {
    if (head != nullptr) heap.push(head);
  }

  ListNode dummy(0);
  ListNode* tail = &dummy;
  while (!heap.empty()) {
    ListNode* node = heap.top();
    heap.pop();
    tail->next = node;
    tail = node;
    if (node->next != nullptr) heap.push(node->next);
  }
  tail->next = nullptr;
  return dummy.next;
}

int main() {
  ListNode a1(1), a2(4), b1(1), b2(3), b3(5);
  a1.next = &a2;
  b1.next = &b2;
  b2.next = &b3;
  for (ListNode* p = mergeKLists({&a1, &b1}); p != nullptr;
       p = p->next) {
    std::cout << p->val << ' ';
  }
  std::cout << '\n';
}

总共弹出、插入各至多 NN 次，时间 O(Nlog⁡k)O(N\log k)，堆空间 O(k)O(k)。空链表不入堆；全部输入耗尽后堆自然变空，循环结束。这个模式同样适用于外部排序、日志分片归并、多个有序迭代器的联合扫描：堆比较的是“当前头”，而不是把所有记录复制进内存。

双堆中位数：边界相接，大小平衡

在线中位数（LeetCode 295）用两个堆分割数据：

  • lower 是最大堆，保存较小的一半，堆顶是左半最大值；
  • upper 是最小堆，保存较大的一半，堆顶是右半最小值。

严格维护两个不变量：

  1. 序关系：任意 lower 元素不大于任意 upper 元素，等价地（两边非空时）lower.top() <= upper.top()；
  2. 大小关系：lower.size() == upper.size() 或 lower.size() == upper.size() + 1。

约定 lower 可以多一个元素。于是总数为奇数时中位数就是 lower.top()；偶数时是两个堆顶的平均数。先把新数按边界放入某堆，再从较大一边移动一个元素给另一边，就不会破坏序关系。

双堆把数据分为较小半与较大半；插入后通过堆顶迁移恢复大小不变量，并由边界元素直接得到中位数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
#include <functional>
#include <iostream>
#include <optional>
#include <queue>
#include <vector>

class MedianFinder {
 public:
  void addNum(int value) {
    if (lower_.empty() || value <= lower_.top()) {
      lower_.push(value);
    } else {
      upper_.push(value);
    }
    rebalance();
  }

  [[nodiscard]] std::optional<double> findMedian() const {
    if (lower_.empty()) return std::nullopt;
    if (lower_.size() > upper_.size()) {
      return static_cast<double>(lower_.top());
    }
    const double left = static_cast<double>(lower_.top());
    const double right = static_cast<double>(upper_.top());
    return (left + right) / 2.0;
  }

 private:
  void rebalance() {
    if (lower_.size() > upper_.size() + 1U) {
      upper_.push(lower_.top());
      lower_.pop();
    } else if (lower_.size() < upper_.size()) {
      lower_.push(upper_.top());
      upper_.pop();
    }
  }

  using MinHeap = std::priority_queue<
      int, std::vector<int>, std::greater<int>>;
  std::priority_queue<int> lower_;
  MinHeap upper_;
};

int main() {
  MedianFinder finder;
  for (int value : {5, 2, 10, 4}) {
    finder.addNum(value);
    std::cout << *finder.findMedian() << ' ';
  }
  std::cout << '\n';
}

每次插入至多做一次跨堆移动，时间 O(log⁡n)O(\log n)；查询中位数 O(1)O(1)；空间 O(n)O(n)。平均值先转换为 double，避免两个很大的 int 在相加时溢出。另一种短写法是始终先推入最大堆、把最大堆顶转移到最小堆、再按大小转回；它也正确，但“按边界插入，再平衡”的版本更直接地暴露不变量。

双堆并不是只适用于中位数。凡是需要持续维护一个分割点、且答案来自分割点两侧边界的流式问题，都可以先问：左侧是否只需最大值，右侧是否只需最小值？若是，两个相反方向的堆常是比全排序更低成本的选择。

调度模型：最少会议室与资源复用

最少会议室（LeetCode 253）的目标是同一时刻并发会议数的峰值。按开始时间排序后，维护一个结束时间最小堆：堆内每个结束时间代表一间正被占用的房间。处理新会议 [start, end) 时，所有 end <= start 的房间都已释放，反复弹出；随后把新会议的结束时间推入。堆大小就是此刻占用房间数，过程最大值即答案。

这里使用半开区间 [start, end)：一场在 10:00 结束、另一场 10:00 开始可以复用同一房间，故判断是 end <= start，不是 <。若题目明确端点也冲突，再改成 <。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
#include <algorithm>
#include <functional>
#include <iostream>
#include <queue>
#include <utility>
#include <vector>

int minMeetingRooms(std::vector<std::pair<int, int>> meetings) {
  std::sort(meetings.begin(), meetings.end());
  using MinHeap = std::priority_queue<
      int, std::vector<int>, std::greater<int>>;
  MinHeap ends;
  int answer = 0;

  for (const auto& [start, end] : meetings) {
    while (!ends.empty() && ends.top() <= start) ends.pop();
    ends.push(end);
    answer = std::max(answer, static_cast<int>(ends.size()));
  }
  return answer;
}

int main() {
  const int rooms = minMeetingRooms({{0, 30}, {5, 10}, {10, 20}});
  std::cout << rooms << '\n';
}

排序耗时 O(nlog⁡n)O(n\log n)，每个结束时间至多进出堆一次，堆部分也是 O(nlog⁡n)O(n\log n)，总空间最坏 O(n)O(n)。这与“按结束时间最早贪心选尽可能多的不重叠会议”不同：后者只需一个结束边界，目标是最大选取数；本题目标是并发峰值，必须保留所有未结束会议。

从建模看，它与服务器实例数、跑道分配、CPU 任务槽、连接池容量完全等价。堆顶应是最早能归还的资源，因为它最可能被下一个请求复用。

选型：堆、排序、平衡树与双端堆

堆只暴露一个极值，正是其快的原因。选结构时先写出每一步真正需要的操作：

需求合适结构原因
反复取全局最小/最大单堆top 为 O(1)O(1)，更新为 O(log⁡n)O(\log n)
一次性完整排序排序输出顺序本来就是目标
流式保留前/后 kk 名固定大小堆空间只随 kk 增长
动态中位数或分位边界双堆两侧边界同时可见
任意键查找与有序遍历平衡树堆不支持按键定位
既要最小又要最大双端优先队列或双结构单一二叉堆只能高效暴露一端
频繁 decrease-key带位置数组的索引堆标准优先队列不能原地改键

图算法常说 Dijkstra 使用“小根堆”，准确地说是用堆维护所有尚可改进的距离候选；旧候选不在堆内更新，而是重复推入，弹出后与 dist[u] 对比跳过。这个“允许陈旧条目”的设计避免了 priority_queue 缺少 decrease-key 的限制，也保留了正确性。

复杂度对照与陷阱清单

常见方案复杂度

场景核心结构时间空间
手写堆 push / pop二叉堆O(log⁡n)O(\log n)O(n)O(n) 存储
自底向上 heapify数组O(n)O(n)O(1)O(1) 额外
堆排序原地最大堆O(nlog⁡n)O(n\log n)O(1)O(1) 额外
第 kk 大大小为 kk 的小根堆O(nlog⁡k)O(n\log k)O(k)O(k)
kk 路归并大小至多 kk 的小根堆O(Nlog⁡k)O(N\log k)O(k)O(k)
在线中位数插入/查询最大堆 + 最小堆O(log⁡n)O(\log n) / O(1)O(1)O(n)O(n)
最少会议室结束时间小根堆O(nlog⁡n)O(n\log n)O(n)O(n)

交卷前逐项检查

  1. 堆不是全局有序。 只能相信 top()；若要按从小到大取完全部元素，必须连续 pop()，总成本 O(nlog⁡n)O(n\log n)。
  2. 比较器方向。 priority_queue 的 comp(a,b) 为真表示 a 比 b 更该靠后；最小堆用 std::greater<T>，自定义时常要写“a.key > b.key”。
  3. k == 0。 固定大小堆没有容量，不能访问堆顶；先返回空答案或题目规定值。
  4. 空堆。 top()、pop() 前先检查 empty()；题目保证合法不代表通用模板该忽略边界。
  5. 耗尽输入。 多路归并只把非空头部入堆；循环条件是堆非空，不要假设每一路长度相同。
  6. 再平衡。 双堆每次插入后立刻恢复大小关系，并确认堆顶序关系；不要只在查询中位数时补救。
  7. 下滤的孩子。 最小堆选较小孩子、最大堆选较大孩子；选错孩子会留下未修复的违例。
  8. 建堆边界。 起点是 n / 2 - 1；用有符号循环变量，避免空数组的无符号下溢。
  9. 元素键变化。 堆内对象的比较字段不能被静默修改；重新入堆或使用版本号跳过陈旧项。
  10. 区间语义。 调度题先确定 [start,end) 还是闭区间，再决定释放条件是 <= 还是 <。

小结

二叉堆把完全二叉树压缩为连续数组，用 parent、left、right 三个公式定位关系；它不排序全体，只维护根到每个后代的局部优先级。插入时上滤、删除根时下滤，自底向上建堆利用高度求和达到 O(n)O(n)。

真正的解题动作是把堆顶解释成“当前最值得处理”或“当前最容易淘汰”的边界：Dijkstra 取最短暂定距离，TopK 淘汰候选里最弱者，多路归并取各路最小头部，调度复用最早释放资源，双堆让两个边界夹住中位数。先写清这个不变量，再选择最大堆、最小堆或双堆，比较器方向与边界条件就不再靠记忆。

标准库堆算法：把任意随机访问区间当作堆

priority_queue 是容器适配器：它替你管理底层 vector，只开放
push、pop、top。当需要在原数组的一段区间上建堆、或希望看到
内部布局时，<algorithm> 还提供四个更底层的算法：

算法效果复杂度
std::make_heap将整个区间原地改造成堆O(n)O(n)
std::push_heap假定最后一个元素新加入，执行上滤O(log⁡n)O(\log n)
std::pop_heap将堆顶换到区间末尾，剩余前缀仍是堆O(log⁡n)O(\log n)
std::sort_heap连续执行 pop_heap，得到升序O(nlog⁡n)O(n\log n)

最容易误解的是 pop_heap：它不会缩短 vector。调用之后，
最大堆的顶被交换到 end() - 1，有效堆范围变成
[begin(), end() - 1)；调用方随后必须 pop_back()。这一设计使
算法可以用于任何随机访问迭代器区间，也正好解释了堆排序的结构。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <algorithm>
#include <iostream>
#include <vector>

int main() {
  std::vector<int> values{3, 1, 6, 5, 2, 4};
  std::make_heap(values.begin(), values.end());
  std::cout << values.front() << '\n';

  values.push_back(8);
  std::push_heap(values.begin(), values.end());
  std::cout << values.front() << '\n';

  std::pop_heap(values.begin(), values.end());
  const int largest = values.back();
  values.pop_back();
  std::cout << largest << ' ' << values.front() << '\n';

  std::sort_heap(values.begin(), values.end());
  for (int value : values) std::cout << value << ' ';
  std::cout << '\n';
}

这些算法默认构建最大堆；若传入 std::greater<int>{}，四个调用必须
全部使用同一比较器，才得到一致的小根堆。只在 make_heap 中传比较器、
后续 push_heap 忘记传，是把一个合法小根堆按最大堆规则修复，结果没有
任何有意义的保证。

priority_queue 的底层与批量建堆

对已有数组，逐个 push 是 O(nlog⁡n)O(n\log n)；而将序列作为构造参数传给
priority_queue，实现可一次 make_heap，复杂度为 O(n)O(n)。在代码
需要先收集一批数据再处理时，后者更符合问题本身。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
#include <functional>
#include <iostream>
#include <queue>
#include <vector>

int main() {
  const std::vector<int> input{7, 1, 9, 2, 6, 3};
  std::priority_queue<int> maxHeap(
      std::less<int>{}, input);
  using MinHeap = std::priority_queue<
      int, std::vector<int>, std::greater<int>>;
  MinHeap minHeap(std::greater<int>{}, input);
  std::cout << maxHeap.top() << ' ' << minHeap.top() << '\n';
}

构造函数的第一个实参是比较器，第二个实参是底层容器；它们的类型必须匹配
模板参数。实际面试或竞赛中，更常写逐个 push 以保持可读性；但要知道
批量建堆是线性的，不要把它误算成 O(nlog⁡n)O(n\log n)。

从不变量推导模板，而不是背代码

手写堆常被写成一串下标操作，结果遇到最大堆、结构体键、需要稳定次序时就
容易改错。更通用的观点是：Compare 描述“谁的优先级更低”，并令堆顶
永远是不满足 Compare(top, x) 的那个最佳元素。下面是一个小型泛型堆；
默认 std::less<T> 因而是最大堆，传 std::greater<T> 则是最小堆。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
#include <functional>
#include <iostream>
#include <optional>
#include <utility>
#include <vector>

template <class T, class Compare = std::less<T>>
class BinaryHeap {
 public:
  explicit BinaryHeap(Compare compare = Compare{})
      : compare_(std::move(compare)) {}

  [[nodiscard]] bool empty() const {
    return data_.empty();
  }

  [[nodiscard]] std::optional<T> top() const {
    if (data_.empty()) return std::nullopt;
    return data_.front();
  }

  void push(T value) {
    data_.push_back(std::move(value));
    siftUp(static_cast<int>(data_.size()) - 1);
  }

  std::optional<T> pop() {
    if (data_.empty()) return std::nullopt;
    T answer = std::move(data_.front());
    if (data_.size() == 1U) {
      data_.pop_back();
      return answer;
    }
    data_.front() = std::move(data_.back());
    data_.pop_back();
    siftDown(0);
    return answer;
  }

 private:
  [[nodiscard]] bool lowerPriority(const T& a, const T& b) const {
    return compare_(a, b);
  }

  void siftUp(int index) {
    while (index > 0) {
      const int p = (index - 1) / 2;
      if (!lowerPriority(data_[p], data_[index])) break;
      std::swap(data_[p], data_[index]);
      index = p;
    }
  }

  void siftDown(int index) {
    const int n = static_cast<int>(data_.size());
    while (index * 2 + 1 < n) {
      int child = index * 2 + 1;
      const int right = child + 1;
      if (right < n && lowerPriority(data_[child], data_[right])) {
        child = right;
      }
      if (!lowerPriority(data_[index], data_[child])) break;
      std::swap(data_[index], data_[child]);
      index = child;
    }
  }

  std::vector<T> data_;
  Compare compare_;
};

int main() {
  BinaryHeap<int, std::greater<int>> minHeap;
  for (int value : {4, 1, 3}) minHeap.push(value);
  while (const auto value = minHeap.pop()) {
    std::cout << *value << ' ';
  }
  std::cout << '\n';
}

这个类展示了比较器抽象的本质，但日常优先选择 std::priority_queue：
标准实现测试更充分，接口也为此任务量身定制。手写模板的价值在于需要
erase(index)、updateKey(index)、记录元素位置等扩展时，能够先从
局部不变量出发，而不是复制一份只适用于 int 最小堆的代码。

索引堆与 decrease-key

普通二叉堆可以在 O(log⁡n)O(\log n) 弹出堆顶，却不能在 O(log⁡n)O(\log n) 找到“编号
为 vv 的元素”在哪里。若键是可定位的整数 id，可额外维护
position[id]：交换 data_[i] 与 data_[j] 时同步交换两者的位置；
这样 decreaseKey(id, newKey) 能先定位到数组位置，再上滤。

不过并非所有问题都值得写索引堆。Dijkstra 常采用懒删除：发现更短距离就
再推入一条 (newDist, v)，旧条目弹出时比较 dist[v] 并跳过。每条边
至多导致一次成功松弛，复杂度仍可接受，代码更短。需要大量真实更新、且
堆中对象数量很大时，索引堆才更有价值。

TopK 的三个等价视角

同一个“第 kk 大”题，常见有三条路线；它们的分界不在于谁更高级，而在
输入是否在线、是否要保存完整顺序、kk 与 nn 的相对大小。

方法时间空间适合情况
排序后取下标O(nlog⁡n)O(n\log n)取决于排序实现还要完整有序数组
快速选择期望 O(n)O(n)O(1)O(1) 额外离线且只要一个顺序统计量
大小为 kk 的小根堆O(nlog⁡k)O(n\log k)O(k)O(k)在线输入、k≪nk\ll n
频率桶O(n)O(n)O(n)O(n)键域来自输入且允许额外桶

固定大小小根堆的严格不变量可写成：处理完前缀后，堆恰含此前出现过的
min(k, count) 个最大元素。新元素若不大于堆顶，前缀中的最大 kk 个
不变；若更大，堆顶是唯一应被淘汰的候选。这个证明也解释了为何“先把全部
元素塞进最大堆、再弹 kk 次”不是同一空间复杂度：它保存了不需要的
n−kn-k 个元素。

第 k 小、最接近 x 与前 K 个对

把“答案集里最容易淘汰者”放在堆顶，是可迁移的模板。

  • 第 kk 小：保留最小 kk 个数，使用大小为 kk 的最大堆；
    堆顶是当前保留集最大者。
  • 最接近 x 的 kk 个数：堆顶放距离最大的候选；可用最大堆保存
    (abs(value-x), value)，超容量就弹出。
  • 两个有序数组的前 kk 小和：小根堆存 (sum, i, j)，每次扩展同一行
    的下一个 j；初始只推每行首元素，避免枚举全部笛卡尔积。

下面的“最接近”版本明确使用 long long 计算距离，避免 int 极值相减
溢出；平局时按数值较大者更容易被淘汰，最终返回值再排序以满足输出约定。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
#include <algorithm>
#include <cstdlib>
#include <iostream>
#include <queue>
#include <utility>
#include <vector>

using Candidate = std::pair<long long, int>;

std::vector<int> closestK(
    const std::vector<int>& values, int x, int k) {
  if (k <= 0) return {};
  std::priority_queue<Candidate> heap;
  for (int value : values) {
    const long long distance =
        std::llabs(static_cast<long long>(value) - x);
    heap.push({distance, value});
    if (static_cast<int>(heap.size()) > k) heap.pop();
  }
  std::vector<int> answer;
  while (!heap.empty()) {
    answer.push_back(heap.top().second);
    heap.pop();
  }
  std::sort(answer.begin(), answer.end());
  return answer;
}

int main() {
  for (int value : closestK({1, 2, 3, 4, 5}, 3, 4)) {
    std::cout << value << ' ';
  }
  std::cout << '\n';
}

注意 std::priority_queue<std::pair<...>> 默认比较 pair 的第一项再比较
第二项。因此距离相同，较大数会先处在最大堆顶并优先淘汰；若题意要求
偏向较大数或保留原始下标，应定义清晰的结构体比较器，而非依赖这个默认。

多路归并的扩展：有序矩阵与最小区间

LeetCode 23 的链表只是“每一路都能给出下一个元素”的一种载体。若输入是
若干升序数组，堆条目应携带值、数组编号、该数组中的位置。弹出一个条目后
仅把同一路的下一个位置推入，因此堆始终不超过路数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
#include <iostream>
#include <queue>
#include <tuple>
#include <vector>

std::vector<int> mergeSortedArrays(
    const std::vector<std::vector<int>>& arrays) {
  using Item = std::tuple<int, int, int>;  // 值、路号、位置
  using MinHeap = std::priority_queue<
      Item, std::vector<Item>, std::greater<Item>>;
  MinHeap heap;
  for (int row = 0; row < static_cast<int>(arrays.size()); ++row) {
    if (!arrays[row].empty()) heap.push({arrays[row][0], row, 0});
  }

  std::vector<int> answer;
  while (!heap.empty()) {
    const auto [value, row, index] = heap.top();
    heap.pop();
    answer.push_back(value);
    const int next = index + 1;
    if (next < static_cast<int>(arrays[row].size())) {
      heap.push({arrays[row][next], row, next});
    }
  }
  return answer;
}

int main() {
  const auto answer = mergeSortedArrays(
      {{1, 4, 7}, {}, {2, 5}, {3, 6, 8}});
  for (int value : answer) std::cout << value << ' ';
  std::cout << '\n';
}

std::tuple 默认按字典序比较，先按值，再按路号与位置；这让相等值的输出
可复现。这里的空数组被跳过，某一路耗尽后也只是不再补充条目。比起将所有
数组拼接后排序的 O(Nlog⁡N)O(N\log N)，它保留了输入已经有序这一信息，取得
O(Nlog⁡k)O(N\log k)。

最小覆盖区间：堆顶给下界，指针给上界

另一类经典题是“从 kk 个升序列表各取至少一个元素，求覆盖它们的最短区间”。
仍然让小根堆保存各路当前元素；同时维护所有当前元素中的最大值
currentMax。堆顶是区间左端点，[heap.top(), currentMax] 是一个
可行区间。弹出最小条目并推进它所在的路，才有机会缩短左端点；任一路耗尽，
就再也无法覆盖所有路，算法结束。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
#include <climits>
#include <iostream>
#include <queue>
#include <tuple>
#include <utility>
#include <vector>

std::pair<int, int> smallestRange(
    const std::vector<std::vector<int>>& lists) {
  using Item = std::tuple<int, int, int>;
  using MinHeap = std::priority_queue<
      Item, std::vector<Item>, std::greater<Item>>;
  MinHeap heap;
  int currentMax = INT_MIN;
  for (int row = 0; row < static_cast<int>(lists.size()); ++row) {
    if (lists[row].empty()) return {0, -1};
    heap.push({lists[row][0], row, 0});
    if (lists[row][0] > currentMax) currentMax = lists[row][0];
  }

  std::pair<int, int> answer{INT_MIN, INT_MAX};
  while (true) {
    const auto [minimum, row, index] = heap.top();
    if (currentMax - minimum < answer.second - answer.first) {
      answer = {minimum, currentMax};
    }
    heap.pop();
    const int next = index + 1;
    if (next == static_cast<int>(lists[row].size())) break;
    const int value = lists[row][next];
    heap.push({value, row, next});
    if (value > currentMax) currentMax = value;
  }
  return answer;
}

int main() {
  const auto [left, right] = smallestRange(
      {{4, 10, 15, 24, 26}, {0, 9, 12, 20}, {5, 18, 22, 30}});
  std::cout << left << ' ' << right << '\n';
}

若多个区间同样短，题目有时要求左端点更小；在更新条件中补上
“长度相等且 minimum < answer.first”即可。这里使用 INT_MIN /
INT_MAX 让第一次有效区间一定更新；若输入范围允许端点相减溢出，应将
长度比较转为 long long。

调度的两种堆建模

“最少会议室”中的堆存结束时间，因为问题只问数量。若题目还要求输出每场
会议分配到哪间具体房间，堆条目改为 (endTime, roomId)；遇到可复用房间时
弹出最早结束的一间，把它的 roomId 交给新会议。房间编号不需要预先知道，
在堆为空或无房间可复用时新建即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
#include <algorithm>
#include <iostream>
#include <queue>
#include <tuple>
#include <utility>
#include <vector>

std::pair<int, std::vector<int>> assignRooms(
    std::vector<std::pair<int, int>> meetings) {
  std::vector<std::tuple<int, int, int>> ordered;
  for (int i = 0; i < static_cast<int>(meetings.size()); ++i) {
    ordered.push_back({meetings[i].first, meetings[i].second, i});
  }
  std::sort(ordered.begin(), ordered.end());

  using Busy = std::pair<int, int>;  // 结束时间、房间号
  using BusyHeap = std::priority_queue<
      Busy, std::vector<Busy>, std::greater<Busy>>;
  BusyHeap busy;
  std::queue<int> freeRooms;
  std::vector<int> assignment(meetings.size());
  int roomCount = 0;

  for (const auto& [start, end, original] : ordered) {
    while (!busy.empty() && busy.top().first <= start) {
      freeRooms.push(busy.top().second);
      busy.pop();
    }
    int room = 0;
    if (freeRooms.empty()) {
      room = roomCount++;
    } else {
      room = freeRooms.front();
      freeRooms.pop();
    }
    assignment[original] = room;
    busy.push({end, room});
  }
  return {roomCount, assignment};
}

int main() {
  const auto [count, rooms] =
      assignRooms({{0, 30}, {5, 10}, {10, 20}, {21, 25}});
  std::cout << count << '\n';
  for (int room : rooms) std::cout << room << ' ';
  std::cout << '\n';
}

这里 freeRooms 只要求任取一个已释放房间，不要求房间号最小，故普通队列
足够。若业务要求“能复用时总选最小编号”，将它换成小根堆即可。这个例子
说明堆通常只承担一个时间维度的瓶颈选择；不要为了“用了堆”而把所有
状态都塞进去。

带冷却时间的任务调度

另一种常见模型是：每个任务有剩余次数，相同任务之间必须间隔若干时间单位。
最大堆存可立即执行任务的剩余次数；等待冷却的任务按“可再次执行的时刻”
组织。若每个时间单位只会释放最早的一批任务，等待区可用队列；若释放时刻
可能乱序，则需第二个最小堆。两个结构分别解决“下一件最值得做的任务”和
“哪个任务最早恢复可用”。这与双堆中位数相似：不同堆承担不同不变量，不能
混为一个比较器。

堆与图搜索：优先级是状态，不是节点

在 图论 的 Dijkstra 中，堆条目应是 (distance, node)，
而不是只放节点编号；在 A* 中，优先级改为 f = g + h；在 Prim 中，优先
级是连接当前生成树的最小边权。三个算法复用了同一个堆操作，却因“何为最佳
候选”的定义不同而解决不同问题。

下面的 Dijkstra 片段单独给出一个容易忽略的安全点：距离相加前确认当前
距离可达，并用足够大的 INF 留出加法空间；同一节点可以多次入堆，旧条目
通过相等性检查淘汰。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
#include <functional>
#include <iostream>
#include <limits>
#include <queue>
#include <utility>
#include <vector>

using Edge = std::pair<int, long long>;
using State = std::pair<long long, int>;

std::vector<long long> dijkstra(
    const std::vector<std::vector<Edge>>& graph, int source) {
  const long long inf = std::numeric_limits<long long>::max() / 4;
  const int n = static_cast<int>(graph.size());
  std::vector<long long> distance(n, inf);
  using StateHeap = std::priority_queue<
      State, std::vector<State>, std::greater<State>>;
  StateHeap heap;
  distance[source] = 0;
  heap.push({0, source});

  while (!heap.empty()) {
    const auto [current, node] = heap.top();
    heap.pop();
    if (current != distance[node]) continue;
    for (const auto& [next, weight] : graph[node]) {
      if (current + weight < distance[next]) {
        distance[next] = current + weight;
        heap.push({distance[next], next});
      }
    }
  }
  return distance;
}

int main() {
  std::vector<std::vector<Edge>> graph(3);
  graph[0] = {{1, 4}, {2, 1}};
  graph[2] = {{1, 2}};
  std::cout << dijkstra(graph, 0)[1] << '\n';
}

堆在这里从未保证“每个节点只出现一次”；它保证的是每次弹出的候选在所有
未处理候选中距离最小。由于边权非负，第一次以最新距离弹出某节点时，该距离
才被最终确定。若有负边，优先队列再精巧也不能修复贪心前提的失败。

实现层面的细节：类型、移动与异常语义

竞赛代码常将堆元素写成 pair<int, int>，这在键值范围小、生命周期简单时
很合适。但有三个细节值得在更长期维护的代码里明确。

  1. 比较键与载荷分离。 若 Task 有名称、状态、时间等字段，比较器只读
    不变量所需的键。堆内任务的这个键保持不可变，或采用版本号。
  2. 避免保存悬垂引用。 priority_queue<T> 按值保存 T；若改为
    priority_queue<T*>，对象所有权必须由其他容器稳定持有。多路链表中
    指针由题目节点池持有，不能把局部临时节点地址推入堆。
  3. 不要用减法比较。 return a.key - b.key > 0 在整数溢出时会反转
    顺序；写成 return a.key > b.key 才是正确的严格弱序。

自定义比较器必须满足严格弱序：comp(x, x) 为假；不能有循环的“更低优先级”
关系；等价元素的判断也要一致。否则堆算法的行为不再受标准契约保护。对于
浮点键，NaN 不具备正常的全序关系，最好在进入堆前拒绝它或定义明确策略。

最终决策表

面对新题，按以下问题顺序判断，通常比先背“堆题题单”更可靠：

  1. 每次是否只需要一个最优候选？若是，考虑单堆。
  2. 答案集合是否固定为 kk 个？若是，堆顶放集合里最差者。
  3. 输入是否由多条有序流组成？若是，堆中只放每条流的当前头部。
  4. 是否有一个分割点，答案取两侧边界？若是，考虑最大堆 + 最小堆。
  5. 是否同时要按键查找、修改任意条目？若是，普通堆可能不够，需要位置表、
    平衡树或哈希索引。
  6. 能否准确说出堆顶代表什么、每次操作后哪个不变量依旧成立？不能时先写出
    这句话，再开始编码。

堆的优势从来不是“神奇地排序”，而是拒绝维护不需要的顺序。把这个取舍看清，
从最短路到 TopK、从合并日志到资源调度的一批问题都会呈现同一个简洁骨架。

复杂度、方向与边界：最后一次对照

上文的模板与变体较多，交卷前把最容易互相混淆的结论压缩如下。表中
n 是已处理元素总数，k 依上下文表示保留数量或输入路数，N 是多路
归并的总元素数。

任务堆顶的语义堆类型关键复杂度
最小值调度当前最早/最小候选小根堆插入、弹出 O(log⁡n)O(\log n)
最大值调度当前最大候选大根堆插入、弹出 O(log⁡n)O(\log n)
第 kk 大已保留答案中最小者大小 kk 的小根堆O(nlog⁡k)O(n\log k)
第 kk 小已保留答案中最大者大小 kk 的大根堆O(nlog⁡k)O(n\log k)
k 路归并各路头部中的最小值小根堆O(Nlog⁡k)O(N\log k)
在线中位数两半部分的相邻边界大根堆 + 小根堆插入 O(log⁡n)O(\log n)，查询 O(1)O(1)
最少资源数正在占用资源中的最早结束时刻小根堆O(nlog⁡n)O(n\log n)
堆排序未就位元素中的最大值原地大根堆O(nlog⁡n)O(n\log n)，O(1)O(1) 额外

比较器再记一遍：std::priority_queue<int> 是大根堆，
std::priority_queue<int, std::vector<int>, std::greater<int>> 是小根堆。
自定义 comp(a, b) 返回 true 的含义不是“a 应在前”，而是“a 的优先级
比 b 低”；故要让 deadline 小的任务先出，写
return a.deadline > b.deadline。在不确定方向时，拿两个元素手算：
若希望 2 在顶而 5 在下，比较器必须认为 5 的优先级低于 2。

边界清单

  • k == 0 或非法 k。 TopK 模板先判断 k <= 0，再创建或访问堆；
    k > n 是否返回全部、返回空或报错由题意决定，但不能悄悄访问空堆顶。
  • 空堆。 通用代码中 top() 和 pop() 必须先判断 empty()；题库若
    保证操作合法，才可以为简洁省略。
  • 输入耗尽。 多路归并只推入非空路；某一路耗尽后不能补入新条目，堆空
    才表示全局耗尽。最小覆盖区间则在任一路耗尽时停止，因为覆盖条件已无法续。
  • 双堆再平衡。 每次插入之后，不是在查询时，恢复
    |lower|-|upper| 的大小约束，并保持左堆所有元素不大于右堆所有元素。
  • 下滤边界。 先确认左孩子存在，再检查右孩子；最小堆应和较小孩子交换，
    最大堆应和较大孩子交换。
  • 堆并非全局有序。 除堆顶外任何两个位置都没有一般的大小关系；不能在
    堆数组上二分查找，也不能把数组顺序当作有序遍历。
  • 更新键。 改变已经在堆内对象的比较字段不会触发重排；用重新入堆 +
    陈旧检查，或实现带位置表的索引堆。
  • 排序稳定性。 堆排序为原地排序，却不是稳定排序；相等键原先的相对顺序
    不受保留。

小结

堆的三件基础事实是：完全二叉树可用 0 下标数组连续表示；siftUp 与
siftDown 只沿一条根叶路径修复局部不变量；从 n / 2 - 1 向根建堆的
总高度工作量是 O(n)O(n)。在此之上，std::priority_queue 提供了可靠的
单端优先队列，而比较器方向决定谁能出现在 top()。

更重要的是建模。固定大小堆把“答案中最差者”露在顶端；多路归并把“每一路
当前头部”放进小根堆；双堆用两个相邻边界给出中位数；会议室问题以最早结束
时间代表最可复用资源。只要先写清堆顶代表什么、每一步后哪些大小与序关系
必须成立，堆题就从模板记忆变成一套可验证的选择过程。