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 = 0,j,k;
for(i =
0;s[i]!='\0';i++)
{
h.r[i+1].key = s[i];
h.length++;
} //建立原始堆
for( i = 2; i
<= h.length; i++ )
{// 逐个插入建堆，提取当前最大值放在父节点
j = i;
while(j!=1) //把H.r[i]插入
{
k = j /
2;
if(LT(h.r[j], h.r[k]))
Swap( h.r[j], h.r[k]);
j =
k;
}
}//for
} //CtreatHeap
时间复杂度是log（n），适合建堆用。
转播
