堆
2025-01-11 15:51:36
发布于：广东
25阅读
0回复
0点赞
#include <bits/stdc++.h>
using namespace std;
const int N=1e6+10;
int len;
int heap[N];
void push(int x){
heap[++len]=x;
int son=len,pa;
while(son>1){
pa=son>>1;
if(heap[son]>=heap[pa]) break;
swap(heap[son],heap[pa]);
son=pa;
}
}
void pop(){
heap[1]=heap[len--];
int pa=1,son;
while((pa<<1)<=len){
son=pa<<1;
if(son<len and heap[son+1]<heap[son]){
son++;
}
if(heap[pa]<=heap[son]) break;
swap(heap[pa],heap[son]);
pa<<=1;
}
}
int top(){
return heap[1];
}
int main(void){
int n;
cin>>n;
for(int i=0;i<n;++i){
int x;
cin>>x;
push(x);
}
for(int i=1;i<=n;++i){
cout<<top()<<" ";
pop();
}
}
有帮助，赞一个