算法刷题笔记 模拟堆（C++实现）

题目描述

• 维护一个集合，初始时集合为空，支持如下几种操作：
  • 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;
}