首页 诗词 字典 板报 句子 名言 友答 励志 学校 网站地图
当前位置: 首页 > 教程频道 > 软件管理 > 软件架构设计 >

为何大顶堆要从后向前逐个调整树?从前向后不可以吗

2013-03-27 
为什么大顶堆要从后向前逐个调整树?从前向后不可以吗?以下伪代码来自《算法导论》BUILD-MAX-HEAP(A)heap-siz

为什么大顶堆要从后向前逐个调整树?从前向后不可以吗?
以下伪代码来自《算法导论》

BUILD-MAX-HEAP(A)
    heap-size[A]←length[A]
    for i←length/2(向下取整)downto 1 //这里为什么是递减的?从1开始递增不行吗?
        do MAX-HEAPIFY(A,i)

MAX-HEAPIFY(A, i)
   l ← LEFT(i)
   r ← RIGHT(i)
   if l ≤ heap-size[A] and A[l] > A[i]
      then largest ← l
      else largest ← i
   if r ≤ heap-size[A] and A[r] > A[largest]
      then largest ← r
   if largest ≠ i
      then exchange A[i] <-> A[largest]
         MAX-HEAPIFY(A, largest) 


求大神帮助!!!为何大顶堆要从后向前逐个调整树?从前向后不可以吗 堆 排序 算法
[解决办法]
仔细看看书

首先,堆维护MAX-HEAPIFY的前提条件是,只有堆顶元素违反堆性质,对其进行调整

建堆BUILD-MAX-HEAP是从后向前调整每一个非叶子结点开始……因为他是调用堆维护MAX-HEAPIFY来建堆的,故而如果要调整当前树,就要首先调整其两棵子树使其满足堆的性质,以保证MAX-HEAPIFY所需要的条件

明白?

热点排行