wanquansanchashu.txt

假设定义堆为满足如下性质的完全三叉树： (1) 空树为堆； (2) 根结点的值不小于所有子树根的值

假设定义堆为满足如下性质的完全三叉树：
(1) 空树为堆；
(2) 根结点的值不小于所有子树根的值，且所有子树
    均为堆。
编写利用上述定义的堆进行排序的算法，并分析推导
算法的时间复杂度。
实现下列函数：
void HeapSort(HeapType &h);

堆（顺序表）的类型HeapType定义如下：
typedef char KeyType;

typedef struct { 
    KeyType key;
    ... ...
} RedType;

typedef struct {
    RedType r[MAXSIZE+1];
    int     length;
} SqList, HeapType;

比较函数和交换函数:
Status LT(RedType a, RedType b)
  { return a.key<b.key ? TRUE : FALSE; }
Status GT(RedType a, RedType b) 
  { return a.key>b.key ? TRUE : FALSE; } 
void Swap(RedType &a, RedType &b)
  { RedType c;  c=a;  a=b;  b=c; }
 void HeapAdjust(HeapType &H,int s,int m)
{RedType rc;
 int j;
 rc=H.r[s];
 for(j=3*s-1;j<=m;j=3*j-1)
 {if(j<m-1)
   {if(LT(H.r[j],H.r[j+1]))
    {++j;
     if(LT(H.r[j],H.r[j+1])) ++j;
    }
    else if(LT(H.r[j],H.r[j+2]))j=j+2;
   }
  else if(j<m)
   if(LT(H.r[j],H.r[j+1])) ++j;  
  if(!LT(rc,H.r[j])) break;
  H.r[s]=H.r[j];s=j;
 } 
 H.r[s]=rc;  
}
void HeapSort(HeapType &h)
/* 元素比较和交换必须调用以下比较函数和交换函数：*/
/* Status LT(RedType a, RedType b);   比较："<"  */
/* Status GT(RedType a, RedType b);   比较：">"  */
/* void Swap(RedType &a, RedType &b); 交换       */
{int i;
 for(i=(h.length+1)/3;i>0;--i)
  HeapAdjust(h,i,h.length);
 for(i=h.length;i>1;--i)
  {Swap(h.r[1],h.r[i]);
   HeapAdjust(h,1,i-1);
  } 

}