阅读量:1
文章目录
题目描述
- 维护一个集合，初始时集合为空，支持如下几种操作：
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; } 