|
问题
如何理解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;
}
|