algorithm - 为数组构建最大堆

Question

我有一道作业题:

Problem 1: Given the array [ 22 | 25 | 71 | 24 | 18 | 5 | 27 | 32 | 104 | 8 | 23 | 66 ] Build a max-heap for the array. Show all steps without skipping any details.

这是我在网上查到的关于max-heap的理解:

最大堆是一个数组，可以更容易地用二叉树表示，其中父节点总是大于它的子节点，并且“每次添加一个子节点时，都会将其添加到左侧，以便每次树增加时它的高度是一棵完整的树”

Anyways this is what I have constructed

我认为这是正确的答案，直到我读到作业中的问题 2 说:

Problem 2: Using the same array as in problem 1, sort the array using Heapsort. Show all steps without skipping any details.

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

Answer 1

您正在构建树，但没有调整数组。数组反射(reflect)了堆结构。第一个元素是数组中最大的元素，接下来的两个元素是该元素的左右子元素。

想法是在构建堆之后交换数组中的最后一个元素和第一个元素，然后在同一个数组上工作，但只使用元素 0 ... array.size - 2。堆条件是无效，您调用 heapify 以在较小的数组上获得正确的堆结构。这再次为您提供了第一个位置的较小数组中的最大元素。您交换较小数组中的第一个和最后一个元素，并在少了 2 个元素的数组上构建堆。但是最后有两个元素被排序(整个数组中最大的元素和下一个最大的元素(这是第一个较小数组中的最大元素))。您将执行此操作，直到您拥有一个没有剩余元素的剩余数组。

看看Heap Sort diagram in the german wikipedia .首先你会看到未排序的数组。较小的黑框表示数组中的位置。第一棵树是堆。

 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

不变的是你的树在每次迭代前后都是一个堆。这就是它起作用的原因。因为您总是会将最大的元素交换到堆化数组的末尾。