[浅显易懂] 数据结构之堆与优先队列(基础篇)

• 堆的概念

• 模拟堆

• 堆排序

• 优先队列——stl容器实现

堆的概念 优先队列

可以查询最大或最小值、插入新元素、删除最大最小值的集合容器称为优先队列， 通过使用二叉堆可以较高效地实现优先队列的插入和查询操作

堆

堆是一棵完全二叉树，即除了最后一层，其它层的结点都是满的，并且最后一层的结点从左到右连续排列的二叉树。

• 大根堆: 父节点的值大于等于子节点的值
• 小根堆: 父节点的值小于等于子节点的值

模拟堆

使用数组模拟堆只需要开一个一维数组，取根节点为下标为1，对每个结点 x , 2 * x 表示该节点的左儿子， 2 * x + 1 表示该节点的右儿子，x / 2 向下取整表示该节点的父亲节点。判断当前结点是否是叶子节点只需要看 2 * x 与 2 * x + 1 是否在当前总结点数范围内即可 。
设总节点数为 n , n 2 frac{n}{2} 2n​ 表示最后一个非叶子节点。

用数组模拟堆实现以下操作:

• 插入一个数
• 求集合当中的最小值
• 删除最小值
• 删除任意一个元素(stl不能直接实现)
• 修改任意一个元素(stl不能直接实现)

这里额外声明两个修正操作，up(x) 以及down(x)
up(x) 用于将结点往堆的上层调整。以小根堆为例，当前结点与其父节点比较，如果其值小于父节点的值，则将其与父节点交换，使其成为新的父节点并继续向上比较，直到其值大于等于父节点或者其成为根节点的时候停止。
down(x)用于将结点往堆的下层调整。以小根堆为例，当前结点与它的两个子节点比较，找到这三个节点的最小值，并与根节点交换，直到当前节点成为叶子节点或者它的值比子节点都小的时候停止。

heap数组: 储存堆的数组
cnt: 当前堆的节点总数

(以下均以小根堆为例)

1.插入: 在最后一个位置插入x

//插入: 最后位置插入x, 对插入的x进行up修正操作
 heap[++ cnt] = x;
 up(cnt);

2.求最小值: 输出堆顶元素

//不管插入还是删除元素，都会进行up和down操作使得堆满足其性质，因此最小值即为小根堆的堆顶元素
cout << heap[1] << endl;

3.删除最小值 (即删除小根堆堆顶元素): 堆末元素代替堆顶元素，删堆末元素，down修复

heap[1] = heap[cnt]; //一维数组删除末尾元素比删除开头元素容易的多，因此用堆末元素代替了堆顶元素并删除原来堆末元素间接实现删除堆顶元素
cnt--; //节点数-1
down(1); //堆末元素已经变成1号节点，对其进行down修正使堆重新稳定

4.删除任意一个元素(stl不能直接实现)

heap[k] = heap[cnt];//仍然是用堆末元素替换要删除的k节点 
cnt--; //节点总数-1
down(k); //这里要分情况讨论，节点小了往上，大了往下，一定会且只会执行up和down修正中的一个操作，两个都写上可避免讨论
up(k);

5.修改任意一个元素(stl不能直接实现)

heap[k] = x; //修改元素只需要直接替换k节点的值并做up和down修正即可
down(k); 
up(k);

修正操作up(x) 和 down(x) 代码 (小根堆)

void up(int u)
{
    while(u / 2 && h[u / 2] > h[u]) //存在父节点，且父节点比当前结点大
    {
        swap(h[u / 2], h[u]); //与父节点交换
        u /= 2; //变为父节点编号也要/2
    }
}

void down(int u) //看u是否是三个节点中的最小值
{
	if(2 * u > cnt) return; // u已经是叶子节点(该行可删)
    int t = u; //用t表示三个节点中最小值
    if(u * 2 <= cnt && h[u * 2] < h[t]) t = u * 2; //存在左儿子并且左儿子值值更小
    if(u * 2 + 1 <= cnt && h[u * 2 + 1] < h[t]) t = u * 2 + 1; //存在右儿子并且右儿子值值更小
    if(u != t) //当前的根节点不是最小值
    {
        swap(h[u], h[t]);
        down(t); //从倒数第二层(叶子节点上一层)开始往上递归
    }
}

例题:
洛谷P3378 堆
直接套模板即可，这里需要通过不断插入新的结点来建堆，n个结点建堆时间复杂度为O(nlogn）， 参考代码如下:

#include 

using namespace std;

typedef long long ll;
const int N = 1e6 + 10;

ll h[N], cnt, n;
#define IOS ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);

void up(int u)
{
    while(u / 2 && h[u / 2] > h[u])
    {
        swap(h[u / 2], h[u]);
        u /= 2;
    }
}

void down(int u)
{
    int t = u;
    if(2 * u <= cnt && h[2 * u] < h[t]) t = 2 * u;
    if(2 * u + 1 <= cnt && h[2 * u + 1] < h[t]) t = 2 * u + 1;
    if(u != t)
    {
        swap(h[u], h[t]);
        down(t);
    }
}
int main()
{
    IOS
    cin >> n;
    for(int i = 1; i <= n; i++)
    {
        int op;
        cin >> op;
        if(op == 1)
        {
            int x;
            cin >> x;
            h[++ cnt] = x;
            up(cnt);
        } 
        else if(op == 2)
        {
            cout << h[1] << endl;
        }
        else
        {
            h[1] = h[cnt];
            cnt--;
            down(1);
        }
    }

    return 0;
}

堆的插入和查询复杂度均为O(nlogn), 查询堆顶元素(小根堆的最小值or大根堆的最大值)复杂度为O(1)

如果一个一个节点插入来建堆的话，n个结点对应建堆时间复杂度为O(nlogn), 实际存在O(n) 建堆的方式

O(n) 复杂度内建堆: 从 n/2 (最后一个非叶子节点)开始down操作
大小根堆只需要调整down中的符号即可

for(int i = 1; i <= n; i++) cin >> h[i]; //读入堆的数据

for(int i = n / 2; i ; i--) down(i); //复杂度为O(n)建堆

这里提供一种不是很严谨的证明方法:
n 2 frac{n}{2} 2n​表示完全二叉树最后一个非叶子结点，也表示最后一层叶子节点数，上面每一层节点数依次为 n 4 frac{n}{4} 4n​, n 8 frac{n}{8} 8n​…, 可以观察到 n 4 frac{n}{4} 4n​ 这一层down到叶子节点需要1步， n 8 frac{n}{8} 8n​这一层需要2步，以此类推，所有的非叶子节点完全down下来需要的步数为 n 4 frac{n}{4} 4n​ * 1 + n 8 frac{n}{8} 8n​ * 2 + n 16 frac{n}{16} 16n​ * 3 + …, 化简即为 n * ( 1 2 2 frac{1}{2^2} 221​ + 2 2 3 frac{2}{2^3} 232​ + 3 2 4 frac{3}{2^4} 243​ + …), 括号部分为差比数列求和，计算可知其< 1, 整体式子乘积< n, 故其总运行步数< n, 即时间复杂度至多为O(n)

堆排序

利用堆也可做排序。先将所有元素都push进去，每次取出堆顶(最小值or最小值)，输出堆顶，弹掉堆顶，直到堆空为止。上述排序方法称为堆排序。

核心思想: 把堆顶一个一个弹出去并不断修复堆

堆排序的时间复杂度为O(nlogn)

例题：
堆排序
(其实就是上面的5种基本操作+up()和down()修正操作+O(n)快速建堆的结合)

#include 

using namespace std;

const int N = 100010;

int n, m;
int h[N], cnt; //cnt存的是当前heap有多少个元素

//堆排序→建堆，每次把堆顶最小的数输出出来

void down(int u) //看u是否是三个点中的最小值
{
    int t = u; //用t表示三个点中最小值
    if(u * 2 <= cnt && h[u * 2] < h[t]) t = u * 2; //存在左儿子并且左儿子值< h[t]
    if(u * 2 + 1 <= cnt && h[u * 2 + 1] < h[t]) t = u * 2 + 1;
    if(u != t) //根节点不是最小值
    {
        swap(h[u], h[t]);
        down(t); //递归处理,从倒数第二层开始往上递归，每一层都为堆
    }
}

void up(int u)
{
    while(u / 2 && h[u / 2] > h[u]) //存在父节点，且父节点比当前结点大
    {
        swap(h[u / 2], h[u]);
        u /= 2;
    }
}
int main()
{
    cin >> n >> m;
    for(int i = 1; i <= n; i++) cin >> h[i];
    cnt = n;

    for(int i = n / 2; i ; i--) down(i); //复杂度为O(n)

    while(m--)
    {
        cout << h[1] << ' '; //输出当前堆顶元素
        h[1] = h[cnt];     //删除堆顶
        cnt--;
        down(1);
    }
    return 0;
}

优先队列——stl容器实现

stl容器中的priority_queue(优先队列)可以实现堆的各种功能 (需要包含头文件)

• 定义: priority_queue<类型> 变量名；
• push() 向堆里插入一个元素
• size() 返回堆的长度
• empty() 返回堆是否为空
• top() 返回堆顶元素
• pop() 弹出堆顶元素

没有clear()!
没有clear()!
没有clear()!

注意: priority_queue默认为大根堆，如果想定义为小根堆常用有两种方法:

1. push(-x)
   -x按照从大到小排序，等价于x按照从小到大排序
2. priority_queue <类型,vecotr <类型>,greater <类型>> 变量名
   如 priority_queue, greater > heap;

例题:

合并果子

题意: 每次可以合并两堆不同种类的果子，每次消耗体力为两堆果子重量和，最终把所有果子合并为一堆，求消耗体力最小的方案
如合并[1, 2, 3, 4, 5]的过程: [1, 2, 3, 4, 5] → [3, 3, 4, 5] → [4, 5, 6] → [6, 9] → [15]

分析: 贪心策略，每次合并最小的两堆，一直操作直到只剩下一堆果子为止。可以维护存放所有果子重量的堆, 每次合并时取出两个最小的，合并后再放回堆中即可

#include 

using namespace std;

priority_queue, greater > q; //小根堆

int main()
{
    int n, x, y, tmp, ans  = 0;
    cin >> n;
    for(int i = 1; i <= n; i++)
    {
        cin >> x;
        q.push(x);
    }
    while(q.size() > 1)
    {
        x = q.top();
        q.pop(); 
        y = q.top();
        q.pop(); //弹出来两个最小值
        tmp = x + y;
        q.push(tmp);
        ans += tmp;
    }
    cout << ans << endl;
    return 0;
}

练习题:

• P3378 【模板】堆
• 模拟堆
• 堆排序
• P1177 【模板】快速排序
• P1090 [NOIP2004 提高组] 合并果子 / [USACO06NOV] Fence Repair G
• P2168 [NOI2015] 荷马史诗
• P2827 [NOIP2016 提高组] 蚯蚓
• P1801 黑匣子
• P1168 中位数
• P1631 序列合并

关于堆的基础部分就到这里结束了，实际上堆的应用还有很多（如优化最短路、构构建哈夫曼树等），将会在后续内容更新。欢迎各位评论区交流指正~