堆排序算法

                                                                                                               ---------- C++博客 Alex-Lee   2009-10-15

      （二叉）堆结构是一种数组对象，它可以被视为一颗完全二叉树。算法时间复杂度O(nlgn)，具有插入排序和合并排序的优点。堆结构满足堆性质：对除根以外的每个节点i,满足A[PARENT(i)] >= A[i]。
   
       堆排序算法实现有三个部分完成：
1，保持堆性质函数heap_ify;
2,构建堆函数build_heap;
3,堆排序函数 heap_sort;
另外，在优先级队列中有extract-max 过程和insert过程，在作业队列中常用，比如消息队列。这部分在优先级排序中说明。

实现:
1,数据元素结构（使用int作为实现版本)
typedef struct int_array
{
 int *pa;
 int array_size;
} INT_ARRAY;

2,swap
void swap(int *pa,int *pb)
{
 int tmp;
 tmp = *pa;
 *pa = *pb;
 *pb = tmp;
}

3, tree child define
//结点标识从0开始算，算其左右孩子结点宏
#define LEFT(i)  2*i +1
#define RIGHT(i) 2*i +2

4,heap_ify
//使得以i给根结点的树满足堆特性a[i]>=a[child(i)]
static void heap_ify(INT_ARRAY *pia,int heap_size,int i)
{
 int left,right,largest;

 left = LEFT(i);
 right = RIGHT(i);

 //找出i结点与其左右孩子结点的值的最大者
 if (left <= heap_size && pia->pa[left] > pia->pa[i])
 {
  largest = left;
 }
 else
 {
  largest = i;
 }
 if (right <= heap_size && pia->pa[right] > pia->pa[largest])
 {
  largest = right;
 }

 if (largest != i)
 {//如果i结点值比子结点值小，那么与孩子结点最大值交换
  swap(&pia->pa[i],&pia->pa[largest]);
  //保证交换数据后的子树还能满足堆特性
  heap_ify(pia,heap_size,largest);
 }
}
5,build_heap

//创建堆后，整个树满足a[parent(i)]>=a[i]；
static void build_heap(INT_ARRAY *pia)
{
 int i;
 for (i = pia->array_size/2;i >= 0 ;--i)
 {
  heap_ify(pia,pia->array_size,i);
 }
}
6,heap_sort
//首先创建堆，由于a[0]总是保存最大树，
//将a[0]置换到a[n-i]，这样完成升序排序。
void heap_sort(INT_ARRAY *pia)
{
 int i,heap_size;
 heap_size = pia->array_size -1;
 build_heap(pia);
 //print_sort(pa,len,"after build heap");
 for (i = pia->array_size -1; i > 0;--i)
 {
  swap(&pia->pa[0],&pia->pa[i]);
  heap_size --;
  heap_ify(pia,heap_size,0);
 }
}

代码：heap-sort算法代码
堆排序算法效率还是不错的，虽然可能比不上快速排序，今天测试了2次，1千万整数排序不超过20秒。