自学内容网 自学内容网

算法刷题笔记 模拟堆(C++实现)

题目描述

  • 维护一个集合,初始时集合为空,支持如下几种操作:
    • I x,插入一个数x
    • PM,输出当前集合中的最小值;
    • DM,删除当前集合中的最小值(数据保证此时的最小值唯一)
    • D k,删除第k个插入的数;
    • C k x,修改第k个插入的数,将其变为x
  • 现在要进行N次操作,对于所有第2个操作,输出当前集合的最小值。

输入格式

  • 第一行包含整数N
  • 接下来N行,每行包含一个操作指令,操作指令为I xPMDMD kC 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;
}

原文地址:https://blog.csdn.net/hanmo22357/article/details/140483590

免责声明:本站文章内容转载自网络资源,如本站内容侵犯了原著者的合法权益,可联系本站删除。更多内容请关注自学内容网(zxcms.com)!