【数据结构】堆的应用(小根堆)

2023-12-16 22:33:00

知识概览

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

小根堆与大根堆:

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

堆的存储:

一维数组用来存下来一棵树。在堆中,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算法基础课

文章来源:https://blog.csdn.net/u012181348/article/details/134907142
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。