模拟堆

// 1.插入一个数 heap[++size]==x;up(size);
// 2.求集合中的最小值 heap[1];
// 3.删除最小值 heap[1]=heap[size];size--;down(1);
// 4.删除任意一个元素 heap[k]=heap[size];size--;up(k),down(k);
// 5.修改任意一个元素 heap[k]=x;down(k),up(k);

//1.模拟一个堆，并由小到大输出m个数
// #include<iostream>
// #include<algorithm>

// using namespace std;
// const int N=100010;
// int n,m;
// int h[N],asize;//size为尾部

// void down(int u)
// {
//     int t=u;
//     if(u*2<=asize&&h[u*2]<h[t])t=u*2;//判断下左
//     if(u*2+1<=asize&&h[u*2+1]<h[t])t=u*2+1;//判断下右
//     if(u!=t)//发生交换，值也应该交换
//     {
//         swap(h[u],h[t]);
//         down(t);//继续往下递归
//     }
// }

// int main()
// {

//     cin>>n>>m;
//     for(int i=1;i<=n;i++)cin>>h[i];
//     asize=n;

//     for(int i=n/2;i;i--)down(i);

//     //从小到大输出
//     while(m--)
//     {
//         cout<<h[1];
//         h[1]=h[asize];
//         asize--;
//         down(1);
//     }
//     return 0;
// }


//2.堆的一系列操作
#include <iostream>
#include<string.h>
#include<algorithm>
using namespace std;

const int N=10010;
int n,m;
int h[N],asize;
int ph[N],hp[N];//ph[k]->第k个插入的数的下标是什么，//hp[k]->下标是k的点是第几个插入的


//题目中第k个插入，这里的k相当于链表中的idx，是节点的唯一标识
// //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]]); //根据a和b的位置找到它们分别是第几个插入的元素，然后将其（在h数组中的）"下标"转换

    //不能swap(a,b),当你swap后就是把二者的所有的东西都换了，放在原题相当于什么都没有改
    //也就没有达成要求---转化下标
    swap(hp[a],hp[b]);
    swap(h[a],h[b]);
}

void down(int u)
{
    int t=u;
    if(u*2<=asize&&h[u*2]<h[t])t=u*2;//判断下左
    if(u*2+1<=asize&&h[u*2+1]<h[t])t=u*2+1;//判断下右
    if(u!=t)//发生交换，值也应该交换
    {
        heap_swap(t,u);
        down(t);//继续往下递归
    }
}

void up(int u)
{
    while(u/2&&h[u/2]>h[u])//往上判断
    {
        heap_swap(u/2,u);
        u/=2;//把u赋为改变后的值
    }
}

int main()
{


    scanf("%d",&n);
    while(n--)
    {
        char op[10];
        int k,x;
        scanf("%s",op);
        //插入
        if(!strcmp(op,"I"))
        {
            scanf("%d",&x);
            m++;
            asize++;
            ph[m]=asize,hp[asize]=m;
            h[asize]=x;
            up(asize);
        }
        //输出堆顶
        else if(!strcmp(op,"PM"))printf("%d\n",h[1]);
        //删除堆顶
        else if(!strcmp(op,"DM"))
        {
            heap_swap(1,asize);
            asize--;
            down(1);
        }
        //删除第k个插入的数
        else if(!strcmp(op,"D"))
        {
            scanf("%d",&k);
            k=ph[k];
            heap_swap(k,asize);
            asize--;
            up(k),down(k);
        }
        //改变第k个插入的数
        else
        {
            scanf("%d%d",&k,&x);
            k=ph[k];
            h[k]=x;
            down(k),up(k);
        }
    }
    return 0;
}