839. 模拟堆

题目

维护一个集合，初始时集合为空，支持如下几种操作：

I x，插入一个数 x；
PM，输出当前集合中的最小值；
DM，删除当前集合中的最小值（数据保证此时的最小值唯一）；
D k，删除第 k 个插入的数；
C k x，修改第 k 个插入的数，将其变为 x；
现在要进行 N 次操作，对于所有第 2 个操作，输出当前集合的最小值。

输入格式
第一行包含整数 N。

接下来 N 行，每行包含一个操作指令，操作指令为 I x，PM，DM，D k 或 C k x 中的一种。

输出格式
对于每个输出指令 PM，输出一个结果，表示当前集合中的最小值。

每个结果占一行。

数据范围
1≤N≤105
−109≤x≤109
数据保证合法。

输入样例：
8
I -10
PM
I -10
D 1
C 2 8
I 6
PM
DM
输出样例：
-10
6

代码

#include <iostream>
#include <cstring>

using namespace std;

const int N = 100010;

int h[N], cnt;
int hp[N], ph[N];

void exchange(int a, int b)
{
    
    swap(ph[hp[a]], ph[hp[b]]);//交换存储堆节点的当前所在位置，即更新a节点所在的新的位置和b节点所在的新的位置
    swap(hp[a], hp[b]);//交换a节点在在ph数组中的索引的值，跟b节点在ph数组中的索引的值
    swap(h[a], h[b]);//交换堆的两个节点的值
}

void down(int u)
{
    
    int t = u;
    if(2*u <= cnt && h[2*u] < h[t]) t = 2*u;
    if(2*u+1 <= cnt && h[2*u+1] < h[t]) t = 2*u+1;
    if(t != u)//如果需要往下交换
    {
    
        exchange(t, u);//交换堆中父节点跟两个子节点中的较小值
        down(t);//继续交换堆中三个值中的较小值
    }
}

void up(int u)
{
    
    while(u/2 && h[u] < h[u/2])//如果u节点的父节点存在，并且u节点的值<u/2节点的值
    {
    
        exchange(u, u/2);//交换堆中u和u/2位置的节点
        u/=2;//继续判断父节点
    }
}


int main()
{
    
    int n;
    cin >> n;
    
    int m = 0;
    
    while (n -- )
    {
    
        char op[5];
        int k, x;
        cin >> op;
        
        
        if(!strcmp(op,"I"))//如果需要插入一个新的堆节点
        {
    
            cin >> x;
            cnt++;//堆节点的个数
            m ++ ;//插入的次数，作为索引
            
            ph[m] = cnt; //第m次插入的堆节点的位置为cnt， 因为此时堆元素的值为h[cnt]
            hp[cnt] = m; //第cnt个堆节点在ph数组中的索引为m，即上一行代码ph[m]中的m，即建立双向映射关系

            h[cnt] = x;//给插入的堆节点赋值
            up(cnt);//插入到堆底的新节点往上走
        }
        else if(!strcmp(op,"PM"))
        {
    
            cout<<h[1]<<endl;
        }
        else if(!strcmp(op,"DM"))
        {
    
            exchange(1,cnt--);//交换堆顶元素跟堆的末尾元素
            down(1);//down操作
        }
        else if(!strcmp(op,"D"))
        {
    
            cin >> k;
            k = ph[k];//第k个插入的数的当前位置
            exchange(k,cnt--);//把第k个数当前所在的位置跟cnt作为参数，进行交换
            down(k);
            up(k);
        }
        else if(!strcmp(op,"C"))
        {
    
            cin >> k >> x;
            k = ph[k];//获取第k个插入的数的当前位置
            h[k] = x;//修改第k个插入的元素
            down(k);
            up(k);
        }
    }
    
    
    return 0;
}