14.模拟堆

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 const int N = 100010;
 4 int h[N], se;
 5 int ph[N], hp[N];
 6 //ph[k]存储第k个插入的数在堆里的下标
 7 //hp[k]堆里面的点是第几个插入的点 
 8 void heap_swap(int a, int b) {
 9     swap(ph[hp[a]], ph[hp[b]]);
10     swap(hp[a], hp[b]); 
11     swap(h[a], h[b]); //交换两个值
12 } 
13 void down(int u) {
14     int t = u;
15     if (u * 2 <= se && h[u * 2] < h[t]) {
16         t = u * 2;
17     }
18     if (u * 2 + 1 <= se && h[u * 2 + 1] < h[t]) {
19         t = u * 2 + 1;
20     }
21     if (u != t) {
22         heap_swap(u, t);
23         down(t);
24     }
25 }
26 void up(int u) {
27     while (u / 2 && h[u / 2] > h[u]) {
28         heap_swap(u / 2, u);
29         u /= 2;
30     }
31 }
32 int main() {
33     int n;
34     cin >> n;
35     int m = 0; //表示是当前第几个插入的数
36     while (n--) {
37         string s;
38         int k, x;
39         cin >> s;
40         if (s == "I") {
41             cin >> x;
42             se++;
43             m++;
44             ph[m] = se; //插入新的数，放在末尾
45             hp[se] = m;
46             h[se] = x;
47             up(se);
48         } else if (s == "PM") {
49             cout << h[1] << endl;
50         } else if (s == "DM") {
51             heap_swap(1, se);
52             se--;
53             down(1);
54         } else if (s == "D") {
55             cin >> k;
56             k = ph[k]; //让k等于第k个插入的数在堆里面的位置
57             heap_swap(k, se);
58             se--;
59             down(k);
60             up(k);
61         } else {
62             cin >> k >> x;
63             k = ph[k];
64             h[k] = x;
65             down(k);
66             up(k);
67         }
68     }
69     return 0;
70 }