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

admin2023-02-06 43

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

选项

答案算法如下： [*] 设该堆对应的树高为h，则满足h≤log₂R．len，调整是自底向上查找，最多查找到树根，所以时间复杂度为O(log₂R．len)。

解析

转载请注明原文地址:https://kaotiyun.com/show/bEwD777K

计算机408

相关试题推荐

随机试题

最新回复(0)