|
楼主
楼主 |
发表于 2018-9-7 21:42:03
|
只看该作者
堆排序
- #include<iostream>
- using namespace std;
- int heap[100001],a,len,n,m,b;
- void swap(int &q,int &p)
- {
- int t=q;
- q=p;p=t;
- }
- void push(int x)
- {
- heap[++len]=x;
- n=len;
- while(heap[n/2]>heap[n] && n>1)
- {
- swap(heap[n/2],heap[n]);
- n/=2;
- }
- }
- int get()
- {
- int k=heap[1],next;
- heap[1]=heap[len--];
- n=1;
- while(n+n<=len)
- {
- next=n+n;
- if(next<len && heap[next+1]<heap[next])next++;
- if(heap[n]<=heap[next])break;
- swap(heap[n],heap[next]);
- n=next;
- }
- return k;
- }
- int main()
- {
- cin>>m;
- for(int i=1;i<=m;i++)
- {
- cin>>b;
- push(b);
- }
- while(len>0)cout<<get()<<endl;
- return 0;
- }
复制代码 |
|