http://acm.hdu.edu.cn/showproblem.php?pid=1040
题意：普通的排序题，用来练习排序。
思路：从小到大排，用大顶堆。
堆排序，有两个函数：
HeapSort()：
(1)、对每个有孩子的节点从大到小依次调整，从而构建成大顶堆；
(2)、每次将堆顶和当前堆最后元素交换，然后对除了最后一个元素的堆调整。
HeapAdjust()：
和自己的儿子比较，若儿子比母亲大，则儿子值赋给母亲，儿子变成下一位母亲，遍历下一层。否则调整结束。
#include <stdio.h> #include <algorithm> #include <string.h> #include <queue> #include <iostream> using namespace std; typedef long long ll; const int N = 1005; const int INF = 0x3f3f3f3f; int num[N]; void HeapAdjust(int mother, int len) { int tmp = num[mother]; for(int i = 2*mother; i <= len; i*=2) { if(i<len && num[i]<num[i+1]) i++; if(num[i]<=tmp) break;//若儿子没有母亲大，则调整完毕 num[mother] = num[i]; mother = i; } num[mother] = tmp; } void HeapSort(int len) { for(int i = len/2; i > 0; i--) { HeapAdjust(i, len); } for(int i = len; i > 1; i--) { swap(num[1], num[i]); HeapAdjust(1, i-1); } } int main() { // freopen("in.txt", "r", stdin); int t, n; scanf("%d", &t); while(t--) { scanf("%d", &n); memset(num, 0, sizeof(num)); for(int i = 1; i <= n; i++) scanf("%d", &num[i]); HeapSort(n); for(int i = 1; i < n; i++) printf("%d ", num[i]); printf("%d\n", num[n]); } return 0; }
