模拟堆的实现

问题
如何理解AcWing 模拟堆这道题中的heap_swap，hp[N], ph[N]？

详解
重点：题目中第k个插入，这里的k相当于链表中的idx，是节点的唯一标识
不理解idx到底是啥意思的可以先看看这篇，其中总结了对链表，Trie树，堆中idx的理解：https://www.acwing.com/solution/content/5673/

1. 关于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联系在一起了吗？

2. 理解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个插入元素
删除操作，三个步骤：

1. 找到第idx个插入元素在堆数组中的位置（堆数组下标）
2. 与堆尾元素交换
3. 在原来第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
#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()< 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;
}