AcWing 839 模拟堆
维护一个集合，初始时集合为空，支持如下几种操作：
I x，插入一个数 x；
PM，输出当前集合中的最小值；
DM，删除当前集合中的最小值（数据保证此时的最小值唯一）；
D k，删除第 k 个插入的数；
C k x，修改第 k 个插入的数，将其变为 x ；
现在要进行 N 次操作，对于所有第 2 个操作，输出当前集合的最小值。
输入格式
第一行包含整数 N。
接下来 N 行，每行包含一个操作指令，操作指令为 I
x，PM，DM，D
k 或 C k x中的一种。
输出格式
对于每个输出指令 PM，输出一个结果，表示当前集合中的最小值。
每个结果占一行。
数据范围
\(1≤N≤10^5\)
\(−10^9≤x≤10^9\)
数据保证合法。
输入样例
>8
I -10
PM
I -10
D 1
C 2 8
I 6
PM
DM
输出样例
>-10
6
问题分析
该题的难点在于实现按照元素插入顺序删除或修改的操作。可以通过额外构建一个数组ph[]来进行记录，数组的下标值自然的成为元素的插入序数，其中的元素值则表示该元素在堆数组中的下标。通过数组实现了一组映射关系。
在堆的调整过程中，ph[]数组也应随之进行调整。例如，在将堆数组中下标为a和b的两个元素进行交换时，则应将ph[]数组中元素值为a和b的两个元素进行交换。可以通过查找的方法在ph[]中找到这两个元素再进行交换，但是这样会有较大的耗时。
为了降低查找导致的时间复杂度，可以再构建一个数组hp[]，该数组的下标值表示该元素在堆数组中的下标，其中的元素值则表示元素的插入序数。可以发现，通过ph[]和ph[]两个数组就实现了元素插入序数和该元素在堆数组中的下标的双向映射。在对ph[]数组进行调整时，就可以根据hp[]数组直接获得要交换的两个元素的下标，实现时间复杂度为o(1)的交换操作。
不难发现，h[]数组和hp[]数组的下标含义相同，因此也可以构建一个二维数组h[N][2]，其中第一行存储元素值，第二行存储元素的插入顺序。
两种方式均在下面实现。
代码实现 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172//构建一维数组h[]、ph[]、hp[]实现
using namespace std;
const int N = 100010;
//为实现按插入顺序的删除与修改，需要额外创建两个数组ph[]与hp[]。
//其中，ph[]按插入顺序记录各个元素在堆数组h[]中的下标；hp[]则按堆数组顺序记录各元素是第几个插入的
//因此有hp[ph[a]] = a, ph[hp[a]] = a;
int n, m, cnt, h[N], ph[N], hp[N];
//在交换堆数组中的元素时，ph[]和hp[]数组的值也要进行交换
void heap_swap (int x, int y){
swap (ph[hp[x]], ph[hp[y]]);
swap (hp[x], hp[y]);
swap (h[x], h[y]);
}
//向下调整
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 (t != u)
{
heap_swap (t, u);
down (t);
}
}
//向上调整
void up (int u){
while (u / 2 && h[u] < h[u / 2])
{
heap_swap (u, u / 2);
u >>= 1;
}
}
int main(){
scanf("%d", &n);
cnt = 0, m = 0;
while (n -- )
{
char cmd[2];
int x, k;
scanf("%s", &cmd);
//插入指令：读取要插入的值x,将其添加至堆的最末端，同时更新ph[]与hp[]数组，再向上调整
if (!strcmp (cmd, "I"))
{
scanf("%d", &x);
h[++ cnt] = x;
ph[++ m] = cnt;
hp[cnt] = m;
up (cnt);
}
//输出最小值指令：输出堆数组第一个元素
else if (!strcmp (cmd, "PM")) printf ("%d\n", h[1]);
//删除最小值指令：将堆数组第一个元素与末端元素交换，将堆尺寸缩小1，再从堆顶向下调整
else if (!strcmp (cmd, "DM"))
{
heap_swap (1, cnt --);
down (1);
}
//删除第k个插入的元素：将第k个插入的元素与末端元素交换，将堆尺寸缩小1，再从该元素所在位置向上/向下调整
else if (!strcmp (cmd, "D"))
{
scanf("%d", &k);
k = ph[k];//根据ph[]数组将k修改为该元素此时在堆数组中的下标值
heap_swap (k, cnt --);
down (k);
up (k);
}
//修改第k个插入的元素：将第k个插入的元素修改，在从该元素所在位置向上/向下调整
else
{
scanf("%d%d", &k, &x);
k = ph[k];
h[k] = x;
down (k);
up (k);
}
}
return 0;
}
//构建二维数组h[N][2]、ph[N]实现
using namespace std;
const int N = 100010;
int n, m, cnt, h[N][2], ph[N];
void heap_swap (int x, int y)
{
swap (ph[h[x][1]], ph[h[y][1]]);
swap (h[x][0], h[y][0]);
swap (h[x][1], h[y][1]);
}
void down (int u)
{
int t = u;
if (u * 2 <= cnt && h[u * 2][0] < h[t][0]) t = u * 2;
if (u * 2 + 1 <= cnt && h[u * 2 + 1][0] < h[t][0]) t = u * 2 + 1;
if (t != u)
{
heap_swap (t, u);
down (t);
}
}
void up (int u)
{
while (u / 2 && h[u][0] < h[u / 2][0])
{
heap_swap (u, u / 2);
u >>= 1;
}
}
int main()
{
scanf("%d", &n);
cnt = 0, m = 0;
while (n -- )
{
char cmd[2];
int x, k;
scanf("%s", &cmd);
if (!strcmp (cmd, "I"))
{
scanf("%d", &x);
h[++ cnt][0] = x;
ph[++ m] = cnt;
h[cnt][1] = m;
up (cnt);
}
else if (!strcmp (cmd, "PM")) printf ("%d\n", h[1][0]);
else if (!strcmp (cmd, "DM"))
{
heap_swap (1, cnt --);
down (1);
}
else if (!strcmp (cmd, "D"))
{
scanf("%d", &k);
k = ph[k];
heap_swap (k, cnt --);
down (k);
up (k);
}
else
{
scanf("%d%d", &k, &x);
k = ph[k];
h[k][0] = x;
down (k);
up (k);
}
}
return 0;
}