【数据结构】堆的应用（小根堆）

知识概览

堆用来维护一个数据集合。堆是一个二叉树，可以说是二叉树的一个应用，堆还是一个完全二叉树。

小根堆与大根堆：

• 小根堆是每个点都满足它小于等于左右两边的点。
• 大根堆是每个点都满足它大于等于左右两边的点。

堆的存储：

一维数组用来存下来一棵树。在堆中，x的左儿子是2x，右儿子是2x + 1，1号点是根节点。

如何手写一个堆？

1. 插入一个数：heap[++size] = x; up(size);
2. 求集合当中的最小值：heap[1];
3. 删除最小值：heap[1] = heap[size]; size--; down(1);
4. 删除任意一个元素：heap[k] = heap[size]; size--; down(k); up(k);
5. 修改任意一个元素：heap[k] = x; down(k); up(k);

其中，down(x)表示在一个小根堆中，当一个数变大之后往下调整；up(x)表示在一个小根堆中，当一个数变小之后往上调整。1-3操作在C++的STL中的priority_queue中有实现，但是4、5需要间接实现，这是手写堆的一个好处，在Dijkstra（迪杰斯特拉）算法的堆优化中会有用到。

例题展示

题目链接

https://www.acwing.com/problem/content/840/

代码

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 100010;

int n, m;
int h[N], cnt;

void down(int u)
{
    int t = u;
    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);
    }
}

int main()
{
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++) scanf("%d", &h[i]);
    cnt = n;
    
    for (int i = n / 2; i; i--) down(i);
    
    while (m--)
    {
        printf("%d ", h[1]);
        swap(h[1], h[cnt--]);
        down(1);
    }
    
    return 0;
}

题目链接

https://www.acwing.com/problem/content/841/

代码

#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

const int N = 100010;

int h[N], ph[N], hp[N], cnt;

void heap_swap(int a, int b)
{
    swap(ph[hp[a]], ph[hp[b]]);
    swap(hp[a], hp[b]);
    swap(h[a], h[b]);
}

void down(int u)
{
    int t = u;
    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)
    {
        heap_swap(u, t);
        down(t);
    }
}

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

int main()
{
    int n, m = 0;
    scanf("%d", &n);
    while (n--)
    {
        char op[5];
        int k, x;
        
        scanf("%s", op);
        if (!strcmp(op, "I"))
        {
            scanf("%d", &x);
            cnt++;
            m++;
            ph[m] = cnt, hp[cnt] = m;
            h[cnt] = x;
            up(cnt);
        }
        else if (!strcmp(op, "PM")) printf("%d\n", h[1]);
        else if (!strcmp(op, "DM"))
        {
            heap_swap(1, cnt);
            cnt--;
            down(1);
        }
        else if (!strcmp(op, "D"))
        {
            scanf("%d", &k);
            k = ph[k];
            heap_swap(k, cnt);
            cnt--;
            down(k), up(k);
        }
        else
        {
            scanf("%d%d", &k, &x);
            k = ph[k];
            h[k] = x;
            down(k), up(k);
        }
    }
}

参考资料

1. AcWing算法基础课