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

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

admin2017-01-04  55
问题 写一个HeapInsen(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．1en／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)。
解析
转载请注明原文地址:https://kaotiyun.com/show/bQRi777K
本试题收录于： 计算机408题库学硕统考专业分类
0

计算机408

学硕统考专业

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