A.length和A.heap-size有什么区别？

Question

我有一个关于堆排序的问题.它在算法书中说明A.heap-size<= A.length 我不理解两者之间的区别.如果数组表示堆,为什么有可能A.heap-size小于A.length.我知道这A.heap-size表示堆内元素的数量,为什么它不完全只等于数组中的项数？

Answer 1

只是为了扩大答案.进一步阅读那本书.

A.heap_size一个数组,是放置heap(max_heap或min_heap)结构元素的地方.它在排序或排队的范围内是有意义的.你是对的:这是一个堆内元素的数量,但它等于A.length只有第一次迭代堆排序.

在下一次迭代中,在将max_heap tree(A[1])的根与A[i] = A[A.length](数组A中的最后一个元素)交换之后,该A[1]元素将是A的最后一个元素,并且A.heap_sort值将减少1并且max_heap结构应该是max_heapified : A[Parent(i)] >= A[i],其中Parent(i)返回堆树的i/2.

Answer 2

堆排序的不变量是n元素数组的前k个元素是k个最小元素上的堆,最后n个k元素是排序顺序中的n-k个最大元素.后面的元素是堆不占用整个数组的原因.