堆排序Heapsort
堆排序是一个优秀的算法，但是在实际应用中，之前介绍的快速排序Quicksort的性能一般会优于堆排序，但是堆排序仍有很多应用
e.g.作为高效的优先队列
优先队列（priority queue）是一种用来维护由一组元素构成的集合S的数据结构，其中的每一个元素都有一个相关的值，称为关键字（key），一个最大优先队列支持以下操作：
①INSERT(S,x)把元素x插入集合S中
②MAXIMUM(S)返回S中具有最大键字的元素
③EXTRACT-MAX(S)去掉并返回S中的最有最大键字的元素
④INCREASE-KEY(S,x,k)将元素x的关键字增加到k，这里假设k的值不小于x的原关键字值
相应的，最小优先队列支持以下操作：
INSERT、MINIMUM、EXTRACT-MIN、DECREASE-KEY
显然，优先队列可以用堆来实现。在用堆来实现优先队列时，需要在堆中的每个元素里存储对应对象的句柄（handle）
时间复杂度分析：堆排序Heapsort的时间复杂度为O（lg n），因为除了时间复杂度为O（lg n）的MAX-HEAPIFY以外，它的其他操作都是常数阶的
下附堆排序Heapsort程序
#include<cstdio> using namespace std; int a[1000]; int n,m; void adjust_heap(int k) { int i,t,p; t=k; if(2*k<=m && a[2*k]>a[t]) { t=2*k; } if(2*k+1<=m && a[2*k+1]>a[t]) { t=2*k+1; } if(t!=k) { p=a[k]; a[k]=a[t]; a[t]=p; adjust_heap(t); } } void build_heap() { int i; for (i=m/2;i>=1;i--) { adjust_heap(i); } } void heap_sort() { int p; build_heap(); while (m>0) { p=a[1]; a[1]=a[m]; a[m]=p; m--; adjust_heap(1); } } int main() { int p,i; scanf("%d",&n); m=n; for(i=1;i<=n;i++) { scanf("%d",&a[i]); } heap_sort(); for(i=1;i<=n;i++) { printf("%d ",a[i]); } }