21.模拟堆

• 堆的时间复杂度
  操作所花的时间都和树的深度成正比 ,因此为O（logn）

• 初始化小根堆的时间复杂度
  

  O（n）

堆排序

#include<iostream>
#include<algorithm>
using namespace std;
const int N=1e5+10;
int n,m,s;
int h[N];
void down(int u)
{
    int t=u;
    if(u*2<=s&&h[u*2]<h[t]) t=u*2;//判断左儿子是否比当前的结点要小
    if(u*2+1<=s&&h[u*2+1]<h[t]) t=u*2+1;//判断右儿子是否比当前的结点要小
    if(u!=t)
    {
        swap(h[t],h[u]);
        down(t);
    }
}
int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++) cin>>h[i];
    s=n;
    for(int i=n/2;i;i--) down(i);
    while(m--)
    {
        cout<<h[1]<<" ";
        h[1]=h[s];
        s--;
        down(1);
    }
    return 0;
}

模拟堆

查找元素时需要知道它在当前堆中的位置在哪里，才好进行 down 或 up，所以需要hp数组（第几个插入的数字 对应 目前堆里的位置），但是单纯swap交换数字，不会改变位置指针，所以需要ph数组来用作位置指针(目前堆里的位置 对应 第几个插入的数字）

#include<bits/stdc++.h>
#include<algorithm>
#include<cstring>
using namespace std;
const int N=1e5+10;
char str[2];
int hp[N],ph[N],h[N];
int SIZE;
void heap_swap(int a,int b)
{
//这里的两个swap先后位置没有影响的
    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(u*2<=SIZE&&h[u*2]<h[t]) t=u*2;
    if(u*2+1<=SIZE&&h[u*2+1]<h[t]) t=u*2+1;
    if(t!=u)
    {
        heap_swap(t,u);
        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--)
    {
        int x,k;
        cin>>str;
        if(!strcmp(str,"I"))
        {
            scanf("%d",&x);
            SIZE++;
            m++;
            hp[SIZE]=m,ph[m]=SIZE;
            h[SIZE]=x;
            up(SIZE);
        }
        else if(!strcmp(str,"PM"))cout<<h[1]<<endl;
        else if(!strcmp(str,"DM"))
        {
            heap_swap(1,SIZE);
            SIZE--;
            down(1);
        }
        else if(!strcmp(str,"D"))//删除第k个插入的数
        {
            scanf("%d",&k);
            k=hp[k];
            heap_swap(k,SIZE);
            up(k);
            down(k);
        }
        else if(!strcmp(str,"C"))//修改第k个数，将其变为x
        {
            scanf("%d%d",&k,&x);
            k=hp[k];
            h[k]=x;
            up(k);
            down(k);
        }
    }
    return 0;
}