Heap sorting

堆排序比较特殊，采用数组表示堆。

先将数组表示成大根堆或者小根堆。然后从堆中依次取根，最后形成有序序列。

#include<bits/stdc++.h>
using namespace std;const int N = 1e5 + 10;
int a[N];void bigheap(int* a, int start, int len)
{if(start < 0 || len == 1) return;int son = start * 2 + 1;int parent = start;while(son <= len){if((son+1 <= len) && (a[son] < a[son+1])){son = son+1;}if(a[parent] > a[son]){break;}int tmp = a[son];a[son] = a[parent];a[parent] = tmp;parent = son;son = parent * 2 + 1;}
}
void heapsort(int* a, int len)
{for(int i = len/2-1; i>=0; i--){bigheap(a, i, len-1);}for(int i = len - 1; i > 0; i--){int tmp = a[i];a[i] = a[0];a[0] = tmp;bigheap(a, 0, i-1);}}
int main() {int n;cin >> n;for (int i = 0; i < n; ++i) {cin >> a[i];}heapsort(a, n);for (int i = 0; i < n; ++i) {cout << a[i] << ' ';}
}