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

本文主要是介绍【数据结构】堆的应用（小根堆），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

知识概览

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

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

一维数组用来存下来一棵树。在堆中，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);}}
}

这篇关于【数据结构】堆的应用（小根堆）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---