10.35.c

数据结构习题及答案

10.35③  假设定义堆为满足如下性质的完全三叉树：
(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 Adjust(HeapType &h,int s,int m);
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/3;i>0;i--) Adjust(h,i,h.length);
  for(i=h.length;i>1;i--)
  {
    Swap(h.r[1],h.r[i]);
    Adjust(h,1,i-1);
  }
}
void Adjust(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&&LT(h.r[j],h.r[j+1])){j++; if(j<m&&LT(h.r[j],h.r[j+1]))j++;}
    else if(j<m-1&&LT(h.r[j],h.r[j+2])) j+=2;
    if(!LT(rc,h.r[j])) break;
    h.r[s]=h.r[j];
    s=j;
  }
  h.r[s]=rc;
}