首页 > 代码库 > AC日记——二叉堆练习3 codevs 3110
AC日记——二叉堆练习3 codevs 3110
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[500001],n; public: void up(int now) { if(now<=1) return ; int front=now>>1; 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<<1)<=n) blc=true,vlc=heap[now<<1]; else blc=false; if((now<<1|1)<=n) brc=true,vrc=heap[now<<1|1]; else brc=false; if(blc) { if(vlc<heap[next]) { next=now<<1; } } if(brc) { if(vrc<heap[next]) { next=now<<1|1; } } if(next!=now) { swap(heap[next],heap[now]); down(next); } } void push(int cur_) { n++; heap[n]=cur_; up(n); } void pop() { heap[1]=heap[n]; n--; down(1); } int top() { return heap[1]; }};class T_heap heap;int n,ai;int main(){ scanf("%d",&n); for(int i=1;i<=n;i++) { scanf("%d",&ai); heap.push(ai); } for(int i=1;i<=n;i++) { printf("%d ",heap.top()); heap.pop(); } return 0;}
AC日记——二叉堆练习3 codevs 3110
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。