问题
如何理解AcWing 模拟堆这道题中的heap_swap，hp[N], ph[N]？
详解
重点：题目中第k个插入，这里的k相当于链表中的idx，是节点的唯一标识
不理解idx到底是啥意思的可以先看看这篇，其中总结了对链表，Trie树，堆中idx的理解：https://www.acwing.com/solution/content/5673/
- 关于idx
堆中的每次插入都是在堆尾，但是堆中经常有up和down操作。所以节点与节点的关系并不是用一个ne[idx][2]可以很好地维护的。但是好在堆是个完全二叉树。子父节点的关系可以通过下标来联系（左儿子2n，右儿子2n+1）。就数组模拟来说，知道数组的下标就知道结点在堆中的位置。所以核心就在于即使有down和up操作也能维护堆数组的下标（k）和结点（idx）的映射关系。 比如说：h[k] = x, h数组存的是节点的值，按理来说应该h[idx]来存，但是节点位置总是在变的，因此维护k和idx的映射关系就好啦
举例： 用ph数组来表示ph[idx] = k(idx到下标), 那么结点值为h[ph[idx]], 儿子为ph[idx] * 2和ph[idx] * 2 + 1, 这样值和儿子结点不就可以通过idx联系在一起了吗？
- 理解hp与ph数组
从上面讨论的可以知道，ph数组主要用于帮助从idx映射到下标k，似乎有了ph数组就可以完成所有操作了，但为什么还要有一个hp数组呢？
原因就在于在swap操作中我们输入是堆数组的下标，无法知道每个堆数组的k下标对应idx（第idx个插入），所以需要hp数组方便查找idx。
void heap_swap(int a, int b) { swap(ph[hp[a]], ph[hp[b]]); swap(hp[a], hp[b]); swap(h[a], h[b]); }
3. 举例：堆中的插入操作
注意： 在堆这个数据结构中，数据的插入都是插入到堆尾，然后再up
if (op == “I”) { scanf(“%d”, &x); size ++ ; idx ++ ; //记录第几次插入（设置新的idx） ph[idx] = size, hp[size] = idx; //每次插入都是在堆尾插入（设置ph与hp） h[ph[idx]] = x; //记录插入的值 up(ph[idx]); }
4. 举例：删除第idx个插入元素
删除操作，三个步骤：
- 找到第idx个插入元素在堆数组中的位置（堆数组下标）
- 与堆尾元素交换
- 在原来第idx个元素所在的位置进行down和up操作。（up，down，swap操作的都输入都是下标）
很显然，在第一步中，显然ph[idx]查找即可。第二步，直接swap操作。第三步需要找到原来第idx的元素所在的位置，由于交换完后ph[idx]的值变了，变为堆尾的下标了，所以必须要在之前保存ph[idx]的值
if (op == “D”) { scanf(“%d”, &idx); k = ph[idx]; //必须要保存当前被删除结点的下标 heap_swap(k, size);//第idx个插入的元素移到了堆尾，此时ph[idx]指向堆尾 size --; //删除堆尾 up(k);//k是之前记录被删除的结点的下标 down(k); }
题目描述
blablabla
样例
blablabla
作弊使用multiset
C++ 代码
//Author:ex_jason #include<bits/stdc++.h> #define N 500010 #define NN 5010 #define NNN 510 #define INF 0x3f3f3f3f #define pi 3.1415926535897932384626433 typedef long long ll; const int mod=1e9+7; using namespace std; int a[N],cnt=0; int main() { int n; multiset s; cin>>n; for (int i=1;i<=n;i++) { string t; int x,y; cin>>t; if (t==“I”) { cin>>x; s.insert(x); a[++cnt]=x; } if (t==“PM”) cout<<*s.begin()<<endl; if (t==“DM”) s.erase(s.find(*s.begin())); if (t==“D”) { cin>>x; if (s.find(a[x])!=s.end()) s.erase(s.find(a[x])); } if (t==“C”) { cin>>x>>y; if (s.find(a[x])!=s.end()) s.erase(s.find(a[x])); a[x]=y; s.insert(y); } } return 0; }
