堆排序算法

                                                                                                               ---------- 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秒。