首页 > 代码库 > 算法导论 第六章 思考题 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 用插入的方法建堆