acwing839模拟堆，堆（复杂模板）（模板）

一般大根堆和小根堆可以用优先队列，但解决“把第n个插入数修改成x”类似的问题可能要用模拟堆

如果题目是先只修改，最后询问最小，可以先记录插入顺序修改插入顺序，然后输进堆中进行询问

如果询问后有修改第n插入、删除第n插入，就要模拟堆：

模拟堆板子：

#include <bits/stdc++.h>
using namespace std;

int n,k,x;
const int N=100009;
int ph[N],h[N],hp[N],size=0,m=0;//ph:普通插入位置对应的堆位置；hp：堆位置对应普通插入位置；h：堆中各位置对应数值

void heap_swap(int a,int b){//堆中交换函数（传入的是堆的位置）
    swap(ph[hp[a]],ph[hp[b]]);
    swap(hp[a],hp[b]);
    swap(h[a],h[b]);
}
void up(int x){//向上更新
    while(x>>1&&h[x]<h[x>>1]) {
        heap_swap(x,x>>1); x>>=1;
    }
}
void down(int x){//向下更新
    int p=x;
    if(x<<1<=size&&h[x<<1]<h[p]) p=x<<1;//如果左儿子小于父节点
    if((x<<1|1)<=size&&h[x<<1|1]<h[p]) p=x<<1|1;//右儿子
    if(p!=x){//如果父节点不是最小
        heap_swap(p,x);//交换父节点和较小儿子
        down(p);//继续更新原父节点（现在换成了儿子的位置）
    }
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    cin>>n;
    while(n--){
        string op;
        cin>>op;
        if(op=="I"){//插入x进堆
            cin>>x;
            size++, m++;
            h[size]=x, hp[size]=m, ph[m]=size;
        	up(size);//down不能增加
        }else if(op=="PM") cout<<h[1]<<endl;//输出最小值
        else if(op=="DM"){//删除最小值
            heap_swap(1,size);
	    size--;
            down(1);
        }else if(op=="D"){//删除第k个插入值
            cin>>k;
            k=ph[k];//令k指向插入值所在堆的位置
            heap_swap(k,size);
            size--;
            up(k);
            down(k);
        }else{//把第k个插入值改成x
            cin>>k>>x;
            k=ph[k];
            h[k]=x;
            up(k);
            down(k);
        }
    }
}

注意几点：

1.为什么要hp，ph；

因为题目“删除当前集合中的最小值”是从堆位置影响到普通插入位置；

而“删除第k个插入的数；”，“修改第k个插入的数，将其变为x”是从普通插入位置影响到堆位置

所以要有堆到插入顺序、插入顺序到堆的映射

正确代码：
else if(op=="D"){//删除第k个插入值
            cin>>k;
            k=ph[k];//令k指向插入值所在堆的位置
            heap_swap(k,size);
            size--;
            up(k);
            down(k);
}
原错误代码
else if(op=="D"){
	    cin>>k;  heap_swap(ph[k],size);
	    size--;
	    down(ph[k]);
	    up(ph[k]);
}

为什么错：