堆排序

#include<iostream>
#include<cstdio>

using namespace std;
int n,t,a;
int heap[500010];

void heap_up(int now)
{
    if(now<=1) return;
    int top=now>>1;
    if(heap[now]<heap[top])
     {
         swap(heap[now],heap[top]);
            heap_up(top);
     }
}

void heap_down(int now)
{
    if(now>n) return;
    int lc,rc,next=now;
      bool blc,brc;
    if((now << 1)<=n) blc=true,lc=heap[now << 1];
    else blc=false;
    if((now << 1 | 1)<=n) brc=true,rc=heap[now << 1 | 1];
    else brc=false;
    if(blc)
    {
        if(heap[next]>lc)
          next=now<<1;
    }
    if(brc)
    {
        if(heap[next]>rc)
          next=now << 1 | 1;
    }
    if(next!=now)
    {
        swap(heap[next],heap[now]);
          heap_down(next);
    }
}

void heap_pop()
{
    heap[1]=heap[n];
    n--;
    heap_down(1);
}

void make_heap(int x)
{
    t++;
    heap[t]=x;
    heap_up(t);
}

int main()
{
    scanf("%d",&n);
    int m=n;
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&a);
        make_heap(a);
    }
    for(int i=1;i<=m;i++)
    {
        printf("%d ",heap[1]);
        heap_pop();
    }
    return 0;
}