【模板】堆排序

#include <iostream> #include <cstdio> #include <cstring> #include <algorithm> using namespace std; const int MAXN = 1000005; int n,s,heap[MAXN],cnt = 0; //小根堆 stl默认大根堆 void pop(){ heap[1] = heap[cnt]; int p = 1; while(p * 2 + 1 <= cnt){ int l = p * 2,r = p * 2 + 1; if(heap[l] < heap[p]){ if(heap[r] < heap[l] && heap[r] < heap[p]) swap(l,r);//!!!! swap(heap[l],heap[p]); p = l; } else if(heap[r] < heap[p]){ swap(heap[r],heap[p]); p = r; } else break; } cnt --; } void push(int x){ cnt ++; int p = cnt; heap[p] = x; //顺序…… while(p != 1){ int f = p / 2;//!!!!!! if(heap[f] > heap[p]){ swap(heap[f],heap[p]), p = f; } else break; } } int main(){ scanf("%d",&n); for(int i = 1; i <= n; i ++) scanf("%d",&s),push(s); for(int i = 1; i <= n; i ++) printf("%d ",heap[1]),pop(); return 0; }