我有一个关于堆排序的问题。这说明在算法书 A.heap尺寸和LT =则为a.length 我不理解这两者之间的区别。如果再$ P $阵列psents堆，为什么会出现一种可能性，即 A.heap尺寸小于则为a.length 。我知道， A.heap尺寸重presents堆内元素的数量，那么，为什么不能完全只相当于项目数的数组中？

I have a question about heap sort. It state in an Algorithms book that A.heap-size<= A.length I don’t understand the difference between the two. If an array represents a heap, why is there a possibility that A.heap-size is less than A.length. I know that A.heap-size represents the number of elements inside a heap, so why is it not completely only equal to the number of items inside an array?

推荐答案

堆排序的不变的是，第n个元素的数组的第k个元素是堆在K最小的元素，最后n - K元素是N - K的有序最大的元素。后者的元素是为什么堆不占用整个数组。

The invariant of heap sort is that the first k elements of the n-element array are a heap on the k smallest elements, and the last n - k elements are the n - k largest elements in sorted order. The latter elements are why the heap does not occupy the whole array.