三、例题，代码
AcWing 838. 堆排序
本题链接：AcWing 838. 堆排序
本博客给出本题截图：
关于本题
关于建堆操作，我们当然可以选择一个一个插入的方式，但是，时间复杂度是O(nlogn)，这里给一种更快的建堆方式：
for (int i = n / 2; i; i -- ) down(i);
这样我们建堆的时间复杂度就变成了O(n)
AC代码
#include <iostream> #include <algorithm> using namespace std; const int N = 100010; int h[N], cnt; int n, m; void down(int x) { int t = x; if (x * 2 <= cnt && h[x * 2] < h[t]) t = x * 2; if (x * 2 + 1 <= cnt && h[x * 2 + 1] < h[t]) t = x * 2 + 1; if (t != x) { swap(h[t], h[x]); down(t); } } int main() { scanf("%d%d", &n, &m); cnt = n; for (int i = 1; i <= n; i ++ ) scanf("%d", &h[i]); for (int i = n / 2; i; i -- ) down(i); while (m -- ) { printf("%d ", h[1]); h[1] = h[cnt]; cnt --; down(1); } return 0; }
AcWing 839. 模拟堆
本题链接：AcWing 839. 模拟堆
本博客给出本题截图：
关于本题
这里重新介绍一下交换函数：
因为题目中是删除第k个插入的元素，所以我们需要另外开两个不同的数组：
ph[k]的含义是第k个插入数在堆中的下标
hp[k]的含义是堆中第k个点是第几个插入的点，我们的swap函数重写后为
void heap_swap(int a, int b) { swap(ph[hp[a]],ph[hp[b]]); swap(hp[a], hp[b]); swap(h[a], h[b]); }
AC代码
#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 -- ; up(k); down(k); } else { scanf("%d%d", &k, &x); k = ph[k]; h[k] = x; up(k); down(k); } } return 0; }
四、时间复杂度
关于手写堆各部操作的时间复杂度以及证明，后续会给出详细的说明以及证明过程，目前先鸽了。
