[模板]堆

发布于 2019-04-20  6 次阅读


#include 
using namespace std;
int h[100];
int siftdown(int h[100],int n,int i)
{

    bool done=0;
    if (i*2>n) return 0;
    do
    {
        i=i*2;
        if (i+1<=n&&h[i+1]>h[i]) i++;
        if (h[i/2]h[i/2])
        {
            int t=h[i];
            h[i]=h[i/2];
            h[i/2]=t;
        }
        else done=1;
        i=i/2;
    }
    while (i!=1&&done!=1);
}

int heapinsert(int h[100],int n,int x)
{
    n++;
    h[n]=x;
    siftup(h,n);
}

int heapdelete(int h[100],int n,int i)
{
    int x=h[i],y=h[n];
    n--;
    if (i==n+1) return 0;
    h[i]=y;
    if (y>=x) siftup(h,i);
    else siftdown(h,n,i);
}

int heapdeletemax(int h[100],int n)
{
    heapdelete(h,n,1);
}

int makeheap(int h[100],int n)
{
    for (int i=n/2;i>=1;i--)
        siftdown(h,n,i);
}

int main()
{

    int n;
    scanf("%d",&n);
    for (int i=1;i<=n;i++)
        scanf("%d",&h[i]);

    makeheap(h,n);

    int o=n,j=0;
    for (int i=1;i<=n;i++)
    {
        printf("%d ",h[1]);
        heapdeletemax(h,o);
        o--; 
    }
}
]]>