题目描述
- 维护一个集合,初始时集合为空,支持如下几种操作:
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 ≤ 10^5
−10^9 ≤ x ≤ 10^9
- 数据保证合法。
基本思路
- 模拟堆算法模板用的不多,但是可以用于堆优化迪杰斯特拉等算法中,因此也有必要掌握。
- 实际应用中,和快速排序算法类似,很少自己来写堆,一般来说可以直接利用现有的库来做,但是可能会在面试的过程中遇到需要手写该算法。
- 本题中要求需要能够按照插入顺序随机删除或修改堆中的某个元素,因此需要使用一个额外的数组来存储堆中元素的插入顺序,使得查询该数组时,可以查询到第k个插入的元素在堆中的下标。
实现代码
#include <iostream>
#include <algorithm>
using namespace std;
int n;
string operation;
// heap是堆的数组模拟;p2h记录第K个插入的数在堆数组中的下标;h2p记录堆中下标为K的数是第几个插入的
const int N = 100010;
int heap[N], p2h[N], h2p[N];
// 分别记录当前堆中的元素个数以及已经插入到堆中的元素个数(包括删除的)
int heap_size = 0, total_count = 0;
// 用于交换堆中的两个元素的函数
inline void heap_swap(int index1, int index2)
{
swap(heap[index1], heap[index2]);
int temp1 = h2p[index1], temp2 = h2p[index2];
swap(h2p[index1], h2p[index2]);
swap(p2h[temp1], p2h[temp2]);
}
// 用于将堆中的元素向上移动的函数
void up(int index)
{
if(index >> 1 > 0 && heap[index] < heap[(index >> 1)])
{
heap_swap(index, index >> 1);
up(index >> 1);
}
}
// 用于将堆中的元素向下移动的函数
void down(int index)
{
int temp = index;
if(index * 2 <= heap_size && heap[temp] > heap[index * 2]) temp = index * 2;
if(index * 2 + 1 <= heap_size && heap[temp] > heap[index * 2 + 1]) temp = index * 2 + 1;
if(temp != index)
{
heap_swap(temp, index);
down(temp);
}
}
// 将元素x插入到堆中的函数
void insert_to_heap(int x)
{
++ heap_size;
heap[heap_size] = x;
++ total_count;
p2h[total_count] = heap_size;
h2p[heap_size] = total_count;
up(heap_size);
}
// 输出堆中的最小值的函数
inline void print_min(void)
{
cout << heap[1] << endl;
}
// 删除堆中的最小值的函数
void del_min(void)
{
heap_swap(1, heap_size);
-- heap_size;
down(1);
}
// 删除第K个插入的数的函数
void heap_del(int k)
{
int heap_index = p2h[k];
heap_swap(heap_index, heap_size);
-- heap_size;
up(heap_index);
down(heap_index);
}
// 修改第K个插入的数的函数
void heap_correct(int k, int x)
{
int heap_index = p2h[k];
heap[heap_index] = x;
up(heap_index);
down(heap_index);
}
int main(void)
{
cin >> n;
for(int i = 0; i < n; ++ i)
{
cin >> operation;
if(operation == "I")
{
int x;
cin >> x;
insert_to_heap(x);
}
else if(operation == "PM") print_min();
else if(operation == "DM") del_min();
else if(operation == "D")
{
int k;
cin >> k;
heap_del(k);
}
else if(operation == "C")
{
int k, x;
cin >> k >> x;
heap_correct(k, x);
}
}
return 0;
}