我有一个关于堆排序的问题。它在算法书中指出A.heap-size<= A.length
我不明白两者之间的区别。如果一个数组代表一个堆，为什么会有A.heap-size小于的可能性A.length。我知道它A.heap-size代表堆内元素的数量，那么为什么它不完全等于数组内的项目数呢？
问问题
11639 次
4 回答
8
只是为了扩大答案。进一步阅读那本书。
A.heap_size一个数组，是放置堆（max_heap 或 min_heap）结构元素的地方。它在排序或排队的范围内是有意义的。你是对的：这是堆内元素的数量，但它A.length仅等于堆排序的第一次迭代。
在下一次迭代中，将max_heap树A[1]的根A[i] = A[A.length]（堆树的 i/2。A[1]A.heap_sortA[Parent(i)] >= A[i]Parent(i)
于 2013-11-24T18:58:09.450 回答
5
在堆排序的外部循环的 k 次迭代之后，数组由 n-k 个最小元素（A.heap-size = n-k）上的 n-k 个元素最大堆组成，然后是按排序顺序排列的 k 个最大元素（ A.长度 = n)。
于 2013-09-27T20:52:22.863 回答
2
来自我正在使用的 Cormen's Algorithm 教科书：（这对我有帮助）
于 2017-09-28T20:58:11.947 回答
0
A.length 给出了数组元素的总数，而 A.heap 大小给出了按排序顺序排列的元素的数量或遵循堆属性的元素的数量............和 A.length-A .heap 大小，甚至现在还没有排序，将来必须排序。
于 2017-11-08T16:19:46.610 回答