写一个HeapInsen(R,key)算法,将关键字插入到堆尺中,并保证插入后R仍是堆。请分析算法的时间复杂度。提示:将key先插入R中已有元素的尾部(即原堆的长度加l的位置,插入后堆的长度加1),然后自下往上调整,使插入的关键字满足堆性质。

admin2019-08-15  45

问题 写一个HeapInsen(R,key)算法,将关键字插入到堆尺中,并保证插入后R仍是堆。请分析算法的时间复杂度。提示:将key先插入R中已有元素的尾部(即原堆的长度加l的位置,插入后堆的长度加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.1en].key=key; //增加新值到原堆中已有元素的尾部且堆的长度加1 i=R.len/2; j=R.1en; while(i>0){ //调整为堆 if(R.Rec[i].key<R.Rec[j].key){ R.Rec[0]=R.Rec[i];R.Ree[i]=R.Rec[j];R.Rec[i]=R.Rec[0]; } j=i;i=i/2; //继续自底向上查找 } } 设该堆对应的树高为h,则满足h≤log2R.1en,调整是自底向上查找,最多查找到树根,所以时间复杂度为O(log2R.1en)。

解析
转载请注明原文地址:https://jikaoti.com/ti/bMGjFFFM
0

相关试题推荐
最新回复(0)