题目描述

模拟堆

加上了能够通过插入顺序快速找到堆中元素的映射

开辟数组来分别存放指示插入顺序的数组和堆中位置的数组

C++ 代码

#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int N=100010;
int ph[N];       //指示堆中元素    为了快速的找到第k个插入的数
int hp[N];       //堆中元素在堆中的序号
int h[N];        //堆中元素的值
int sizee;       //堆中元素的个数
int m;           //指示堆中元素序号的序号
void heap_swap(int a,int b)
{
    swap(ph[hp[a]],ph[hp[b]]);  //插入顺序交换
    swap(hp[a],hp[b]);      //插入位置交换
    swap(h[a],h[b]);    //插入数值交换
}
void down(int u)
{
    int t=u;
    if(2*u<=sizee&&h[2*u]<h[t])t=2*u;
    if(2*u+1<=sizee&&h[2*u+1]<h[t])t=2*u+1;
    if(t!=u)
    {
        heap_swap(u,t);
        down(t);
    }
}
void up(int u)
{
    while(u/2&&h[u/2]>h[u])        //截半
    {
        heap_swap(u/2,u);
        u/=2;
    }
}
int main()
{
    int n,m=0;
    cin>>n;
    while(n--)
    {
        char op[10];
        scanf("%s",op);
        int k,x;

        if(!strcmp(op,"I"))
        {
            cin>>x;
            sizee++;
            m++;
            ph[m]=sizee,hp[sizee]=m;     //在m处插入的位置是sizee，在最后一个（sizee）插入的序号是m
            h[sizee]=x;                  //在最后一个插入的值为x
            up(sizee);                   //依次比较往上移
        }
        else if(!strcmp(op,"PM"))cout<<h[1]<<endl;   //根节点是最小的
        //删除最小值，即根节点
        else if(!strcmp(op,"DM"))         
        {
            heap_swap(1,sizee);     //先将根节点换到最下面的位置，方便删除     
            sizee--;                //将元素个数减1，就相当于把最后的节点删除了
            down(1);                //此时根节点就是很大的数，所以依次比较向下移
        }
        else if(!strcmp(op,"D"))
        {
            cin>>k;     
            k=ph[k];                //确定要删除第几个数
            heap_swap(k,sizee);     //将这个数换到最下面
            sizee--;                //和根节点同理
            down(k),up(k);
        }
        else
        {
            cin>>k>>x;           //确定要修改第几个数
            k=ph[k];            //确定要修改数在堆中的位置
            h[k]=x;             //将该位置的数赋值
            down(k),up(k);
        }
    }
    return 0;
}