堆排序算法

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

      （二叉）堆結(jié)構(gòu)是一種數(shù)組對象，它可以被視為一顆完全二叉樹。算法時間復(fù)雜度O(nlgn)，具有插入排序和合并排序的優(yōu)點(diǎn)。堆結(jié)構(gòu)滿足堆性質(zhì)：對除根以外的每個節(jié)點(diǎn)i,滿足A[PARENT(i)] >= A[i]。
   
       堆排序算法實(shí)現(xiàn)有三個部分完成：
1，保持堆性質(zhì)函數(shù)heap_ify;
2,構(gòu)建堆函數(shù)build_heap;
3,堆排序函數(shù) heap_sort;
另外，在優(yōu)先級隊列中有extract-max 過程和insert過程，在作業(yè)隊列中常用，比如消息隊列。這部分在優(yōu)先級排序中說明。

實(shí)現(xiàn):
1,數(shù)據(jù)元素結(jié)構(gòu)（使用int作為實(shí)現(xiàn)版本)
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
//結(jié)點(diǎn)標(biāo)識從0開始算，算其左右孩子結(jié)點(diǎn)宏
#define LEFT(i)  2*i +1
#define RIGHT(i) 2*i +2

4,heap_ify
//使得以i給根結(jié)點(diǎn)的樹滿足堆特性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結(jié)點(diǎn)與其左右孩子結(jié)點(diǎn)的值的最大者
 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結(jié)點(diǎn)值比子結(jié)點(diǎn)值小，那么與孩子結(jié)點(diǎn)最大值交換
  swap(&pia->pa[i],&pia->pa[largest]);
  //保證交換數(shù)據(jù)后的子樹還能滿足堆特性
  heap_ify(pia,heap_size,largest);
 }
}
5,build_heap

//創(chuàng)建堆后，整個樹滿足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
//首先創(chuàng)建堆，由于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千萬整數(shù)排序不超過20秒。