我有一个关于堆排序的问题。它在一本算法书中指出 A.heap-size<= A.length
我不明白两者之间的区别。如果一个数组代表一个堆，为什么有可能 A.heap-size小于 A.length .我知道 A.heap-size表示堆内的元素个数，那为什么不完全只等于数组内的元素个数呢？
最佳答案
只是为了扩展一个答案。进一步阅读那本书。
数组的A.heap_size，是放置堆(max_heap 或min_heap)结构元素的地方。它在排序或排队的范围内是有意义的。你是对的:这是堆内元素的数量，但它仅在堆排序的第一次迭代时等于A.length。
在下一次迭代中，在将 max_heap 树 (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。
关于arrays - A.length 和 A.heap-size 有什么区别？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/19059806/