堆

daniel14311531 · 2018-02-06 16:15:35 · 个人记录

堆

计算机里有堆栈，其中堆是其中之一。堆是一个优先队列，即返回已有数中最值的数。
堆分为大根堆（返回堆中最大数）和小根堆（返回堆中最小数）。下面将展示小根堆。

#include<bits/stdc++.h>
using namespace std;
int h[1000001],n,tmp,size=0,res=0,x;//h储存堆，size为堆中数的数目

void put(int u)//插入一个数
{
    int now,next;
    h[++size]=u;
    now=size;
    while(now>1)
    {
        next=(now>>1);
        if(h[next]<=h[now]) return ;
        int t=h[next];
        h[next]=h[now];
        h[now]=t;
        now=next;
    }
}

int get()//取出一个数
{
    int now,next,ans;
    ans=h[1];
    h[1]=h[size--];
    now=1;
    while(now*2<=size)
    {
        next=now*2;
        if(next<size&&h[next]>h[next+1])    next++;
        if(h[next]>=h[now]) return ans;
        int t=h[next];
        h[next]=h[now];
        h[now]=t;
        now=next;
    }
    return ans;
}

int main()
{
    scanf("%d",&n);
    while(n--)
    {
        scanf("%d",&tmp);
        if(tmp==1)
            scanf("%d",&tmp),put(tmp);
        else if(tmp==2)
            tmp=get(),printf("%d\n",tmp),put(tmp);
        else    tmp=get();
    }
    return 0;
}