每插入一个数,要能修改这个数的值,要能在堆中删除这个数
这两个要求(即完成删除和修改操作) 即获得这个数在堆中的下标,要记录这是第几个插入的数。
所以 核心就是知道第k个插入的数的下标
每个数下标都是插入后 随着down up操作变化 (修改的数也是通过down一遍up一遍变化)
以上两个操作变化数的位置都是通过sort函数,所以要定义一个合适的heap_sort函数。
定义ph函数为第k个插入的数的下标 hp数组为在某下标上的数是第几个
一个合格的heap_sort函数要做到(拥有两个下标a b的前提下)
1. 通过hp更新ph值 (即通过某下标上是第几个数 来修改这个数的下标)swap(ph[hp[a]], ph[hp[b]]);
2. 交换两个堆元素hp值 swap(hp[a], hp[b]);
3. 交换两个堆下标上的元素值 swap(h[a],h[b]);
例如:下标 3 上是第 4 个插入的数 6, 下标 2 上 是第 5 个插入的数 7
(h[3] = 6 hp[3] = 4 ph[4] = 3 ; h[2] = 7 hp[2] = 5 ph[5] = 2 )
交换后应该有:下标 3 上是第 5 个插入的数 7, 下标 2 上 是第 4 个插入的数 6
(h[3] = 7 hp[3] = 5 ph[3] = 5 ; h[2] = 6 hp[2] = 4 ph[4] = 2 )
完成ph交换即swap(ph[hp[a]], ph[hp[b]]), 完成hp值交换即swap(hp[a], hp[b]); ;完成h[]值交换即swap(h[a],h[b]);
#include <iostream>
#include <cstdio>
using namespace std;
const int N = 100010;
int h[N], idx, ph[N], hp[N], cnt;
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 down(int u)
{
int t = u;
if (u * 2 <= cnt && h[u * 2] < h[t]) t = u * 2;
if (u * 2 + 1 <= cnt && h[u * 2 + 1] < h[t]) t = u * 2 + 1;
if (t != u)
{
heap_swap(t, u);
down(t);
}
}
void up(int u)
{
while (u / 2 && h[u / 2] > h[u])
{
heap_swap(u / 2, u);
u >>= 1;
}
}
int main()
{
int n;
scanf("%d", &n);
while (n -- )
{
string op;
int x, k;
cin >> op;
if (op == "I")
{
scanf("%d", &x);
cnt ++ ;
h[cnt] = x;
ph[++ idx] = cnt;
hp[cnt] = idx;
up(cnt);
}
else if (op == "PM") printf("%d\n", h[1]);
else if (op == "DM")
{
heap_swap(1, cnt -- );
down(1);
}
else if (op == "D")
{
scanf("%d", &k);
k = ph[k];
heap_swap(k, cnt --);
up(k);
down(k);
}
else
{
scanf("%d%d", &k, &x);
k = ph[k];
h[k] = x;
up(k);
down(k);
}
}
return 0;
}