Heap



#include

using namespace std;

int heap[100010],cnt=0;

void put(int x)

{

    cnt++;

    heap[cnt]=x;

    int now=cnt;

    int next=cnt;

    while(now>1)

    {

        next=now/2;

        if(heap[next]<=heap[now])break;

        swap(heap[next],heap[now]);

        now=next;

    }

}

int get()

{

    int res=heap[1];

    heap[1]=heap[cnt];

    cnt--;

    int now=1;

    int next=1;

    while(now*2<=cnt)

    {

        next=now*2;

        if(heap[next]>heap[next+1]&&next<=cnt)next++;

        if(heap[next]>=heap[now])break;

        swap(heap[next],heap[now]);

        now=next;

    }

    return res;

}

int main()

{

    int n;

    cin>>n;

    for(int i=1;i<=n;i++)

    {

        int x;

        cin>>x;

        put(x);

    }

    for(int i=1;i<=n;i++)

    {

        cout<<get()<<' ';

    }

    cout<<endl;

    return 0;

}
巴特西

Heap

最新文章

热门文章
