3110 二叉堆练习3
时间限制: 3 s
空间限制: 128000 KB
题目等级 : 黄金 Gold
题解
题目描述 Description
给定N(N≤500,000)和N个整数(较有序)，将其排序后输出。
输入描述 Input Description
N和N个整数
输出描述 Output Description
N个整数(升序)
样例输入 Sample Input
5
12 11 10 8 9
样例输出 Sample Output
8 9 10 11 12
数据范围及提示 Data Size & Hint
对于33%的数据 N≤10000
对于另外33%的数据 N≤100,000 0≤每个数≤1000
对于100%的数据 N≤500,000 0≤每个数≤2*10^9
思路：
手写堆；
来，上代码：
#include <cstdio>
#include <iostream>
#include <algorithm> using namespace std; class T_heap {
private:
int heap[],n; public:
void up(int now)
{
if(now<=) return ;
int front=now>>;
if(heap[front]>heap[now])
{
swap(heap[front],heap[now]);
up(front);
}
} void down(int now)
{
if(now>n) return;
int vlc,vrc,next=now;
bool blc,brc;
if((now<<)<=n) blc=true,vlc=heap[now<<];
else blc=false;
if((now<<|)<=n) brc=true,vrc=heap[now<<|];
else brc=false;
if(blc)
{
if(vlc<heap[next])
{
next=now<<;
}
}
if(brc)
{
if(vrc<heap[next])
{
next=now<<|;
}
}
if(next!=now)
{
swap(heap[next],heap[now]);
down(next);
}
} void push(int cur_)
{
n++;
heap[n]=cur_;
up(n);
} void pop()
{
heap[]=heap[n];
n--;
down();
} int top()
{
return heap[];
}
};
class T_heap heap; int n,ai; int main()
{
scanf("%d",&n);
for(int i=;i<=n;i++)
{
scanf("%d",&ai);
heap.push(ai);
}
for(int i=;i<=n;i++)
{
printf("%d ",heap.top());
heap.pop();
}
return ;
}
