10.34.c

数据结构习题及答案

10.34③ 已知(k1,k2,...,kp)是堆，则可以写一个时
间复杂度为O(log(n))的算法将(k1,k2,...,kp,kp+1)
调整为堆。试编写"从p=1起，逐个插入建堆"的算法，
并讨论由此方法建堆的时间复杂度。

实现下列函数：
void CreateHeap(HeapType &h, char *s);

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

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

typedef struct {
    RedType r[MAXSIZE+1];
    int     length;
} SqList, HeapType;
void CreateHeap(HeapType &h, char *s)
{
 int i,j,k; 
 for(i=0;s[i]!='\0';i++)
   {
    j=i+1;
    h.r[i+1].key=s[i];           //char *s从0下标开始
    h.length++;
    while(j!=1)                  //insert h.r[i+1]
     {k=j/2;      
      if(h.r[j].key<h.r[k].key)  //exchange
        {h.r[0]=h.r[j];
         h.r[j]=h.r[k];
         h.r[k]=h.r[0];
           }//if
      j=k;
      }//while
    }//for   
}