Skip to content

堆与优先队列

大根堆与小根堆、建堆与调整,以及 priority_queue 的用法。

Updated View as Markdown

排序之后取最大值很快,但一边插入新元素一边反复取最大值,排序就不够用了。堆就是为这种场景设计的:插入和取最值都是 O(\log n),而且取最值只要 O(1)。

本章的知识点与 GESP、CSP-J/S 大纲的对应关系如下。

考试 大纲要求 本章位置
CSP-J/S 提高级 2.3.1 优先队列;2.3.3 二叉堆 全章
GESP C++ 六级 考点 6:面向对象(堆的封装思路) 数组模拟堆

堆是什么

堆是一棵完全二叉树,同时满足堆序性质:

  • 大根堆:每个节点的值都不小于它的孩子,根是整棵树的最大值。
  • 小根堆:每个节点的值都不大于它的孩子,根是整棵树的最小值。

因为是完全二叉树,堆可以直接用数组存。下标从 1 开始,节点 i 的关系是:

关系 下标
左孩子 2i
右孩子 2i + 1
父节点 \lfloor i / 2 \rfloor

数组里看到的值不整体有序,但根一定是这个堆里的最值。这是堆和排序数组的关键区别。

两个核心操作

堆的调整围绕两个动作:上浮和下沉。

上浮(插入)

新元素放到数组末尾,然后不断和父节点比较。小根堆里如果它比父节点小就交换,直到比父节点大或者到了根。

int heap[100005], sz = 0; // 小根堆

void push(int x) {
    heap[++sz] = x;
    int i = sz;
    while (i > 1 && heap[i] < heap[i / 2]) {
        swap(heap[i], heap[i / 2]);
        i /= 2;
    }
}

一次上浮最多走树高,复杂度 O(\log n)。

下沉(删除堆顶)

把根和末尾元素交换,删掉末尾,然后让新根不断和较小的孩子比较。小根堆里如果它比孩子大就往下换。

void sink(int i) { // 让 heap[i] 往下沉,直到满足堆序
    while (true) {
        int l = 2 * i, r = 2 * i + 1, smallest = i;
        if (l <= sz && heap[l] < heap[smallest]) smallest = l;
        if (r <= sz && heap[r] < heap[smallest]) smallest = r;
        if (smallest == i) break;
        swap(heap[i], heap[smallest]);
        i = smallest;
    }
}

void pop() {
    heap[1] = heap[sz--]; // 末尾元素提到根
    sink(1);              // 再让它沉下去
}

int top() { return heap[1]; } // 堆顶就是最小值,O(1)

建堆

把一个无序数组调整成堆,从最后一个非叶子节点开始,依次往前做下沉。

void build() {
    for (int i = sz / 2; i >= 1; i--) sink(i);
}

虽然每次下沉是 O(\log n),但对所有节点求和之后总复杂度是 O(n),不是 O(n \log n)。这个结论常考:建堆可以在线性时间内完成。

STL 的 priority_queue

竞赛里几乎不用手写堆,直接用 priority_queue。

#include <bits/stdc++.h>
using namespace std;

int main() {
    priority_queue<int> pq;  // 默认大根堆
    pq.push(3);
    pq.push(1);
    pq.push(4);
    cout << pq.top() << endl; // 4,取最大值
    pq.pop();

    // 小根堆要写全模板参数
    priority_queue<int, vector<int>, greater<int>> minpq;
    minpq.push(3);
    minpq.push(1);
    cout << minpq.top() << endl; // 1

    return 0;
}

pair 自带比较规则,先比第一个再比第二个,所以存 pair<int,int> 时,默认按第一个值从大到小。

要自定义优先级,可以写比较结构体:

struct Node { int id, dis; };

struct Cmp {
    bool operator()(const Node &a, const Node &b) const {
        return a.dis > b.dis; // 想取 dis 最小的,这里写大于
    }
};

priority_queue<Node, vector<Node>, Cmp> pq;

这里的 > 是反直觉的:priority_queue 的队头是「优先级最高」的元素,而比较函数定义的是排序关系,所以想让小值优先,比较函数里要写 a.dis > b.dis。

堆的典型应用

  • 堆排序。反复取堆顶输出,时间 O(n \log n),额外空间 O(1)。
  • Top K 问题。求前 k 大的元素,用一个大小为 k 的小根堆,扫描时把比堆顶大的挤进去,最后堆里就是答案。
  • 合并果子。每次取两个最小的合并,用小根堆实现贪心。
  • Dijkstra 最短路优化。用堆维护当前距离最小的点,复杂度从 O(V^2) 降到 O(E \log V)。
  • 任务调度。按优先级取出下一个要执行的任务。

合并果子的例子:有 4 堆果子,数量分别是 1、2、3、4,每次合并两堆,代价是两堆数量之和,求最小总代价。

每次取最小的两堆:合并 1 和 2 得 3,代价 3;再合并 3 和 3 得 6,代价 6;合并 4 和 6 得 10,代价 10。总代价 3 + 6 + 10 = 19。

这正好是哈夫曼树的构造过程,总代价就是带权路径长度。

复杂度

操作 复杂度
取堆顶 O(1)
插入 O(\log n)
删除堆顶 O(\log n)
建堆 O(n)
查找任意元素 O(n)

堆不擅长查找任意值,也不支持删除任意元素。要删除任意元素,得用能定位元素的高级结构。

常见易错点

  • 堆不保证整体有序,只保证根是最值,别用堆来做「有序遍历」。
  • priority_queue 默认是大根堆,小根堆要用 greater<int>。
  • priority_queue 只能访问堆顶,top() 之前先判断非空。
  • 手写堆时下标从 1 开始,从 0 开始父子下标关系会变。
  • 建堆是 O(n),不要以为必须 O(n \log n) 才行。
  • 自定义比较函数的方向容易反,写完拿两个数据试一下。
  • 该用小根堆的地方写成了默认的大根堆。合并果子、Top K 都必须显式传 greater<T>,忘了 greater 会静默给出错误答案。
  • 求第 k 大用大根堆。方向搞反了:求第 k 大要用小根堆(淘汰最小的),求第 k 小要用大根堆。
  • 合并果子的答案用了 int。n 和 a_i 都不大,但累加起来的代价会超出 int。

练习

练习 1:合并果子

在线评测练习:P1422 合并果子

题目描述

果园里有 n 堆果子,第 i 堆有 a_i 个。每次可以任选两堆合并成一堆,代价为两堆果子数之和。经过 n - 1 次合并后只剩一堆,求最小总代价。

输入格式

第一行包含一个正整数 n;第二行包含 n 个正整数 a_1, a_2, \ldots, a_n,相邻两个整数之间用一个空格隔开。

输出格式

输出一行一个整数,表示最小总代价。

输入输出样例

输入

3
1 2 9

输出

15

(先合并 1 和 2,代价 3;再把 3 和 9 合并,代价 12。总代价 3 + 12 = 15。)

数据范围

  • 1 \le n \le 10^4,1 \le a_i \le 2 \times 10^4。答案可能超出 int,请用 long long。

题目分析

这是堆最经典的应用,也是贪心和堆结合的入门题。

为什么每次取最小的两堆? 因为先被合并的堆会被反复计入后续的代价里(它变成新堆的一部分,之后每次合并都带着它走)。所以越小的堆应该越早合并、被计入的次数越多——这正好是哈夫曼树的思想。反过来,如果先把大的合并,大数会被反复计入,总代价必然更大。

为什么必须用堆? 因为每合并一次就要「重新找出最小的两个」。如果用数组每次排序或线性扫描,复杂度是 O(n^2 \log n) 或 O(n^2);用小根堆,插入和取最小都是 O(\log n),总复杂度 O(n \log n)。

代码骨架非常简单:

  1. 把所有果子数推进小根堆;
  2. 只要堆里还有 2 个以上元素:弹出最小的两个,求和,把和累加进 ans,再把和推回堆;
  3. 最后输出 ans。

两个必须注意的点:

  1. long long。n = 10^4、a_i = 2 \times 10^4 时,总代价可能到 10^9 量级甚至更高,且中间累加更容易溢出。堆的元素类型和 ans 都用 long long。
  2. 小根堆的写法。默认 priority_queue<long long> 是大根堆,会取出最大的两个,答案完全错。必须写全 priority_queue<long long, vector<long long>, greater<long long>>。这是本题最大的坑——代码看起来没问题,思路也对,就是忘了 greater,答案偏大。

参考代码

pq.size() > 1 这个循环条件很关键:只剩一堆时不需要再合并,循环自然结束。不需要单独处理 n = 1 的情况,因为一个元素时循环一次都不进,ans 保持 0,正是正确答案。

练习 2:第 k 大的数(Top K)

题目描述

给定 n 个整数和一个整数 k,求第 k 大的数(重复的数分别占位,即从大到小排序后第 k 个)。

输入格式

第一行两个整数 n 和 k;第二行 n 个整数。

输出格式

输出一个整数,表示第 k 大的数。

输入输出样例

输入

5 2
10 4 7 1 9

输出

9

数据范围

  • 1 \le k \le n \le 10^5,元素在 int 范围内。

题目分析

这题有两条思路,恰好能对比出堆的价值:

思路一:全排序取第 k 个。 sort 一下,复杂度 O(n \log n)。n = 10^5 完全够用,实战中优先这么写。

思路二:大小为 k 的小根堆。 这是 Top K 问题的标准解法,复杂度 O(n \log k):

  1. 用小根堆维护「目前见过的最大的 k 个数」;
  2. 每读入一个数就推进堆;
  3. 如果堆大小超过 k,就弹出堆顶(堆里最小的那个);
  4. 扫完之后,堆里正好是最大的 k 个数,而堆顶就是第 k 大。

为什么小根堆能做到这件事? 因为小根堆的堆顶是「这 k 个里面最小的」,也就是「第 k 大」。每次新来的数如果比堆顶大,就把它挤掉——堆里始终只保留最大的 k 个。

什么时候思路二才有优势?

  • 数据是流式来的(不能全部存下来再排序),比如从日志里实时找前 k 个最大的;
  • n 极大(比如 10^8)而 k 很小(比如 10),此时 O(n \log k) 远优于 O(n \log n);
  • 内存不够存全部数据。

本题 n \le 10^5,两种都能过。但**「用大小为 k 的堆维护 Top K」这个技巧必须掌握**,它是堆最重要的应用模式之一。

一个容易想错的地方:求「第 k 大」用小根堆,求「第 k 小」用大根堆。直觉上是反的,但道理很清楚——要淘汰的是「最不可能是答案的那一端」。求第 k 大时,堆顶是这 k 个里最小的,它最该被更大的数淘汰,所以用小根堆。

参考代码

小结

  • 堆是完全二叉树加堆序性质,根是全局最值。
  • 堆用数组存储,父子下标关系是 2i、2i+1 和 \lfloor i/2 \rfloor。
  • 插入靠上浮,删除堆顶靠下沉,都是 O(\log n);建堆可以 O(n)。
  • 竞赛里用 priority_queue,默认大根堆,小根堆要传 greater。
  • 堆的典型应用是堆排序、Top K、合并果子和 Dijkstra 优化。
  • 合并果子:每次取最小的两个合并,必须用小根堆,答案用 long long。
  • Top K:用大小为 k 的堆,超过 k 就弹出堆顶。求第 k 大用小根堆,求第 k 小用大根堆。
  • 能全排序解决时优先排序(O(n \log n) 常数小);数据流式或 n 极大而 k 很小时,才必须用大小为 k 的堆。
Navigation

Type to search…

↑↓ navigate↵ selectEsc close