模拟堆 – 算法板子leetcode刷题题解

#include<bits/stdc++.h> using namespace std; const int N = 1e5 + 10; int h[N], ph[N], hp[N]; int Size, m, n; 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) {     while (u < Size) {         int t = u;         if (u * 2 <= Size && h[u * 2] < h[t]) t = u * 2;         if (u * 2 + 1 <= Size && h[u * 2 + 1] < h[t]) t = u * 2 + 1;         if (u != t) {             heap_swap(u, t);             u = t;         } else {             break;         }     } }  void up(int x) {     while (x / 2 > 0 && h[x / 2] > h[x]) {         heap_swap(x / 2, x);         x = x / 2;     } }  int main() {     cin >> m;     while(m--) {         char op[10];         scanf("%s", &op);         if (!strcmp(op, "I")) {             int x;             scanf("%d", &x);             ++Size;             ++n;             h[Size] = x;             ph[n] = Size;             hp[Size] = n;             up(Size);         } else if (!strcmp(op, "PM")) {             printf("%dn", h[1]);         } else if (!strcmp(op, "DM")) {             heap_swap(1, Size);             --Size;             down(1);         } else if (!strcmp(op, "D")) {             int k;             scanf("%d", &k);             k = ph[k];             heap_swap(Size, k);             --Size;             down(k), up(k);         } else if (!strcmp(op, "C")) {             int k, x;             scanf("%d%d", &k, &x);             k = ph[k];             h[k] = x;             down(k), up(k);         }     }          return 0; }

模拟堆 – 算法板子leetcode刷题题解部分资料来自网络，侵权毕设源码联系删除