我有一个作业问题说：
问题 1：给定数组 [ 22 | 25 | 71 | 24 | 18 | 5 | 27 | 32 | 104 | 8 | 23 | 66 ] 为数组构建一个最大堆。显示所有步骤而不跳过任何细节。
这是我在互联网上研究对最大堆的理解：
最大堆是一个数组，可以更容易地用二叉树表示，其中父节点总是大于它的子节点，并且“每次添加子节点时，都会将其添加到左侧，以便每次树增加它的高度是一棵完整的树”
我认为这是正确的答案，直到我读到作业的问题 2 说：
问题 2：使用与问题 1 相同的数组，使用 Heapsort 对数组进行排序。显示所有步骤而不跳过任何细节。
现在我很困惑。也许我回答了问题 2...
您正在构建树，但您没有调整阵列。该数组反映了堆结构。第一个元素是数组中最大的元素，接下来的两个元素是该元素的左右子元素。
这个想法是在你构建堆之后交换数组中的最后一个元素和第一个元素，然后在同一个数组上工作，但只使用元素 0 ... array.size - 2。堆条件无效，你调用 heapify 以在较小的数组上获得正确的堆结构。这再次为您提供了第一个位置的那个较小数组中的最大元素。您交换较小数组中的第一个和最后一个元素，并在数组上构建堆，该数组少了 2 个元素。但是最后有两个元素已排序（整个数组中的最大元素和下一个最大元素（这是第一个较小数组中的最大元素））。你会这样做，直到你有一个没有元素的剩余数组。
看看德国维基百科中的堆排序图。首先，您将看到未排序的数组。较小的黑框表示数组中的位置。第一棵树是一个堆。
Unsorted array
23 | 1 | 6 | 19 | 14 | 18 | 8 | 24 | 15
Heapified Array
24 | 23 | 18 | 19 | 14 | 8 | 6 | 1 | 15
First iteration
Swap First (Biggest Element in Array) with last Element (could be anything)
15 | 23 | 18 | 19 | 14 | 8 | 6 | 1 | 24
heap condition is invalid
Build heap on array.size - 2
23 | 19 | 18 | 15 | 14 | 8 | 6 | 1 || 24
Swap first and last element in smaller heap
1 | 19 | 18 | 15 | 14 | 8 | 6 | 23 || 24
Build heap on array.size - 3
19 | 15 | 18 | 1 | 14 | 8 | 6 || 23 | 24
Swap first and last element on that smaller heap and build heap on array.size - 4
until you cant shrink the heap anymore, you'll receive
|| 1 | 8 | 14 | 15 | 18 | 19 | 23 | 24
不变的是，您的树在每次迭代之前和之后都是一个堆。这就是它起作用的原因。因为您将始终将最大的元素交换到 heapified 数组的末尾。