问答题 写一个HeapInsert(R，key)算法，将关键字插入到堆R中，并保证插入后R仍是堆。请分析算法的时间复杂度。 将key先插入R中已有元素的尾部(即原堆的长度加1的位置，插入后堆的长度加1)，然后自下往上调整，使插入的关键字满足堆性质。
算法如下：
typedef struct{
KeyType key;
InfoType otherinfo;
}RecType;
typedef struct{
RecType Rec[MaxNum]; //MaxNum是一个常量
int len;
}SeqList;
HeapInsert(SeqList R, KeyType key){
int i,j;
R.Rec[++R.len].key=key; //增加新值到原堆中已有元素的尾部且堆的长度加1
i=R.len/2; j=R.len;
while(i＞0){ //调整为堆
if(R.Rec[i].key＜R.Rec[j].key){
R.Rec[0]=R.Rec[i]; R.Rec[i]=R.Rec[j]; R.Rec[i]=R.Rec[0];
}
j=i; i=i/2; //继续自底向上查找
}
}
设该堆对应的树高为h，则满足h≤log2R.len，调整是自底向上查找，最多查找到树根，所以时间复杂度为O(log2R.len)。
【正确答案】
【答案解析】算法如下：
typedef struct{
KeyType key;
InfoType otherinfo;
}RecType;
typedef struct{
RecType Rec[MaxNum]; //MaxNum是一个常量
int len;
}SeqList;
HeapInsert(SeqList R, KeyType key){
int i,j;
R.Rec[++R.len].key=key; //增加新值到原堆中已有元素的尾部且堆的长度加1
i=R.len/2; j=R.len;
while(i＞0){ //调整为堆
if(R.Rec[i].key＜R.Rec[j].key){
R.Rec[0]=R.Rec[i]; R.Rec[i]=R.Rec[j]; R.Rec[i]=R.Rec[0];
}
j=i; i=i/2; //继续自底向上查找
}
}
设该堆对应的树高为h，则满足h≤log 2 R.len，调整是自底向上查找，最多查找到树根，所以时间复杂度为O(log 2 R.len)。