算法刷题笔记 模拟堆（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;
}