首页 > 代码库 > 算法导论 第六章 思考题 6-1 用插入的方法建堆
算法导论 第六章 思考题 6-1 用插入的方法建堆
BUILD-MAX-HEAP‘(A) heap-size[A]<-1 for i <- 2 to length[A] do MAX-HEAP-INSERT(A, A[i])
如上,题目给出一种使用插入的办法建堆的算法,而书中6.4节给出的建堆算法如下:
BUILD-MAX-HEAP(A) heap-size[A] <-- length[A] for i <-- length[A] / 2 downto 1 do MAX-HEAPIFY[A, i]
可以发现元素调整的方向恰好反过来了。
现在来考虑问题,第一问看两种方法得到的堆会不会总是一样的,答案是不会,这可以通过举例来说明:
并不是总是一样的,考虑这样一个情况,有一个n=3的数组,其中a[1]<a[2]<a[3],那么在用传统的建堆过程a[1]会变成a[3]的右儿子,而利用BUILD-MAX-HEAP‘(A),a[1]则会变成a[3]的左儿子,于是,建立的堆是不同的。
第二问考虑时间复杂度。可以先参看书中6.4节证明BUILD-MAX-HEAP的时间复杂度时的情形:
在任意高度h上,至多有n/2^(h +1) + 1个节点,而max-heapify作用在高度为h的节点上的时间为O(h),于是得到时间复杂度为:
利用附录中的公式可得建堆的时间复杂度为线性时间O(n)。但是题目中提出的插入建堆方法,元素调整的方向刚好相反,也就是某高度为h的元素作用时间应该变成
O(logn - h),这样的话,代入同样的公式中求得的时间复杂度就变成,O(nlogn)了
算法导论 第六章 思考题 6-1 用插入的方法建堆
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。