知识概览
堆用来维护一个数据集合。堆是一个二叉树，可以说是二叉树的一个应用，堆还是一个完全二叉树。
小根堆：每个点都满足它小于等于左右两边的点。
一维数组用来存下来一棵树。在堆中，x的左儿子是2x，右儿子是2x + 1，1号点是根节点。
如何手写一个堆？
- 插入一个数：heap[++size] = x; up(size);
- 求集合当中的最小值：heap[1];
- 删除最小值：heap[1] = heap[size]; size--; down(1);
- 删除任意一个元素：heap[k] = heap[size]; size--; down(k); up(k);
- 修改任意一个元素：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);}}
}
