//1.什么是堆?
//一个完全二叉树,保证父节点储存的值小于子节点所储存的值
//2.如何储存一个堆
//若该节点的下标为x
//i> x的左儿子为2x
//ii> x的右儿子为2x + 1
//3.核心函数
//i> 下沉:down(int x);
// 将x节点(存的数较大)下沉到正确的位置
//ii> 上浮:up(int x);
// 将x节点(存的数较小)上浮到正确的位置
//4.堆的常见操作
//i> 插入一个数:
// void insert(int x)
// 插入一个数到堆底,然后up到正确的位置
//ii> 求集合中的最小值:
// int get_heap_min()
// 访问堆顶
//iii> 删除最小值:
// void remove_min()
// 交换堆顶与堆尾的值,删除堆尾,堆顶down到正确位置
//iv> 删除任意一个元素:
// void remove(int k)
// 交换k与堆尾的值,删除堆尾(k),然后up或down k下标的值(堆尾)到正确位置
//v> 修改任意一个元素:
// void modify(int k)
// 让下标为k的元素的值改成x,然后up或down k下标的值(堆尾)到正确位置
//5. 堆的初始化
// 将arr数组里的元素初始化为堆:
// void init()
// 将下标i从n/2开始到根节点结束,down(i)
// 为什么?
/*
首先要明确要进行down操作时必须满足左儿子和右儿子已经是个堆。
开始创建堆的时候,元素是随机插入的,所以不能从根节点开始down,
而是要找到满足下面三个性质的结点:
1.左右儿子满足堆的性质。(往上遍历的原因)
2.下标最大(因为要往上遍历)
3.不是叶结点(注意:叶节点一定满足堆的性质,因为只有一个元素)
已知:最后一个节点(下标为n)是叶子节点,满足堆的性质
对于其父节点而言,他要么是右儿子要么是左儿子
根据堆的存储方式:
//若该节点的下标为x
//i> x的左儿子为2x
//ii> x的右儿子为2x + 1
其父节点的下标必然是n/2 (倒数第二层的最后一个)
也就是从该节点开始进行down操作
*/
//6. 额外维护的信息
//i> heap_find_order[N]
// heap -> order,根据堆中的下标寻找插入的顺序
// heap_find_order[b] = j: 在堆中下标为b的数是第j个插入的数
//ii> order_find_heap[N]
// order -> heap,根据插入的顺序寻找堆中的下标
// order_find_heap[i] = a: 第i个插入的数在堆里的下标是a
#include <iostream>
#include <algorithm>
#include <string.h>
using namespace std;
const int N = 100010;
int heap_val[N], order_find_heap[N], heap_find_order[N], idx, order;
//交换堆中下标为a,b的值
void heap_swap(int a, int b)
{
swap(order_find_heap[heap_find_order[a]], order_find_heap[heap_find_order[b]]);
//先更新order_find_heap[N],因为需要通过heap_find_order[N]进行定位
swap(heap_find_order[a], heap_find_order[b]);
//再更新heap_find_order[N]
swap(heap_val[a], heap_val[b]);
//更新堆中所存的值
}
//下沉堆下标为u的节点
void down(int u)
{
int t = u;//t记录值该节点与其左右儿子的值之间最小的节点
int ls = u * 2; //左儿子
int rs = u * 2 + 1; //右儿子
if (ls <= idx && heap_val[ls] < heap_val[t]) //如果左儿子存在并且,左儿子的值比值最小的节点的值小
//将值最小的节点更新为左节点
t = ls;
if (rs <= idx && heap_val[rs] < heap_val[t]) //如果右儿子存在并且,右儿子的值比值最小的节点的值小
//将值最小的节点更新为右节点
t = rs;
if (u != t) //如果最小值节点不是该节点(是儿子节点)
{
//交换
heap_swap(u, t);
//继续down下一个节点(最小的值的节点)
down(t);
}
else
{
//如果最小值节点是该节点
//说明此时该节点符合堆的性质,退出down函数
return;
}
}
//上浮堆下标为u的节点
void up(int u)
{
int f = u / 2; //父节点
while (f != 0 && heap_val[u] < heap_val[f])
//如果父节点存在,且父节点的值大于该节点的值,不符合堆的性质
{
//交换该节点与父节点的值
heap_swap(u, f);
//更新当前节点为父节点
u /= 2;
//更新父节点为爷节点
f /= 2;
}
}
//读入n个数据
void read(int n)
{
//若下标从0开始,则第一的节点的左儿子下标为2*0 = 0,矛盾
for (int i = 1; i <= n; i ++)
scanf("%d", &heap_val[i]);
//更新个数下标idx
idx = n;
}
//将无序数组初始化为堆
void init()
{
for (int i = idx / 2; i >= 1; i --)
down(i);
}
//插入值为x的一个节点
void insert(int x)
{
//插入一个元素,顺序标记和数量标记均加1
idx ++, order ++;
//更新两个映射数组
order_find_heap[order] = idx, heap_find_order[idx] = order;
//更新值为x
heap_val[idx] = x;
//上浮新节点到正确位置
up(idx);
}
//输出最小值
int get_heap_min()
{
return heap_val[1];
}
//移除最小值
void remove_min()
{
heap_swap(1, idx);
idx --;
down(1);
}
//删除堆下标为u的节点
void remove_heap_idx(int u)
{
//与堆尾交换
heap_swap(u, idx);
idx --;
//找到正确的位置
up(u);
down(u);
}
void modify_heap_idx(int u, int x)
{
//修改为x
heap_val[u] = x;
//找到正确的位置
up(u);
down(u);
}
//删除存入第u个插入的值的节点
void remove_order(int u)
{
//找到堆中下标
int k = order_find_heap[u];
//移除
remove_heap_idx(k);
}
void modify_order(int u, int x)
{
//找到堆中下标
int k = order_find_heap[u];
//修改
modify_heap_idx(k, x);
}
int main(int argc, char *argv[])
{
int n;
cin >> n;
while(n --)
{
string op;
int k, x;
cin >> op;
if (op == "I")
{
cin >> x;
insert(x);
}
else if (op == "PM") cout << get_heap_min() << endl;
else if (op == "DM")
{
remove_min();
}
else if (op == "D")
{
cin >> k;
remove_order(k);
}
else
{
cin >> k >> x;
modify_order(k, x);
}
}
return 0;
}