为什么大顶堆要从后向前逐个调整树?从前向后不可以吗?
以下伪代码来自《算法导论》
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所需要的条件
明白?