为数组构建最大堆

Question

我有一个作业问题，内容如下：

问题1：给定数组[22 | 25 | 71 | 24 | 18 | 5 | 27 | 32 | 104 | 8 | 23 | 66]，为该数组构建一个最大堆。展示所有步骤，不要跳过任何细节。

通过在互联网上的研究，我对最大堆有了一些了解：

最大堆是一个数组，可以更容易地用二叉树表示，其中父节点始终大于其子节点，并且“每次添加子节点时，您将其添加到左侧，使得每次树增加高度时都是完全树”。

这是我构建的答案

我认为那是正确的答案，直到我读到我的作业第二个问题说：

问题2：使用与问题1中相同的数组，使用Heapsort（堆排序）对该数组进行排序。展示所有步骤，不要跳过任何细节。

现在我很困惑。也许我回答了问题2...

- Tono Nam

---

链接无法使用。 - Shanu Gupta

Answer 1

您正在构建树，但没有调整您的数组。该数组反映了堆结构。第一个元素是数组中最大的元素，其后两个元素是该元素的左右子节点。

构建堆之后，您需要交换数组中的最后一个元素和第一个元素，然后仅使用元素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

不变量是在每次迭代之前和之后，您的树都是一个堆。这就是为什么它有效的原因。因为您总是将最大的元素交换到堆化数组的末尾。

- ma cılay