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

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

admin2017-11-14  74
问题 写一个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； Heaplnsert(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]．key2R．len，调整是自底向上查找，最多查找到树根，所以时间复杂度 为O(log2R．len)。
解析
转载请注明原文地址:https://www.kaotiyun.com/show/Q3Ri777K
本试题收录于： 计算机408题库学硕统考专业分类
0

计算机408

学硕统考专业

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