用于构建堆的改进算法

Question

我对编程还很陌生，我想了解有关堆排序的某个问题。在我正在阅读的一本书中，有一个用于构建最大堆的修改算法，即：

BuildHeap(A)
    A.heap-size = 1
    for i = 2 to A.length
        Heap-Insert(A, A[i])

所以根据我的理解，这个算法接受一个数组并将堆的大小定义为 1，然后从 2 迭代到数组的总长度，然后将值插入堆。

但这将如何构建最大堆？如果我有一个 [4, 7, 2, 3, 9, 1] 的数组，那么算法不会从值 2 开始，然后简单地将 A[2] 到 A.length 的所有值相加到没有实际构建最大堆的堆？

除了限制堆的总大小外，我不明白 heap-size = 1 在算法中做了什么。我对如何构建最大堆感到困惑。

根据书中所述，普通最大堆的工作原理是首先将每个数组值插入堆中，然后从 A/2 位置开始，然后向后工作并交换大于的值通过调用 Max-Heapify.

评估的当前值

那么这个最大堆将如何工作，因为没有 Max-Heapify(A, largest) 调用，而是只有一个 heap-insert(A, A[i])?

Answer 1

首先，这道题不是关于堆排序的，堆排序只是堆的应用之一。你问的是堆构造.

您提供的伪代码确实是构建堆的另一种（且效率较低）方法，这实际上是许多人在不知道标准算法时会想出的算法弗洛伊德

所以看一下代码：

BuildHeap(A)
    A.heap-size = 1
    for i = 2 to A.length
        Heap-Insert(A, A[i])

该算法的大部分逻辑都包含在 Heap-Insert 函数中，这不仅仅是对数组的简单“追加”：它的作用远不止于此。 Wikipedia 描述隐藏算法如下：

Add the element to the bottom level of the heap at the leftmost open space.

Compare the added element with its parent; if they are in the correct order, stop.

If not, swap the element with its parent and return to the previous step.

你在问题中写下：

there is no Max-Heapify(A, largest)

的确，如果你在使用堆之前就知道最大值是多少就太简单了。你需要先在堆中插入一个值（任何值），然后让堆发挥它的魔力（在Heap-Insert内）以确保最大值最终出现在数组 A 中的第一个（顶部）位置，即 A[1].

引用算法的第一步非常重要：Heap-Insert 期望新值插入末尾。

让我们完成示例 [4, 7, 2, 3, 9, 1]，并放置一个管道符号来指示堆的末尾。开始时，堆大小为 1，所以我们有：

4 | 7   2   3   9   1

让我们在右侧表示一个更具视觉吸引力的二叉树——它只有一个根元素：

4 | 7   2   3   9   1                  4

然后我们调用Heap-Insert(A, A[2])，也就是Heap-Insert(A, 7)。 Heap-Insert 的实现会增加堆的大小，并将该值放在最后一个槽中，所以我们得到：

4   7 | 2   3   9   1                  4
                                      /
                                     7

Heap-Insert 还没有完成——这只是它执行的第一步。现在它“冒泡”了那个引用算法的步骤 2 和 3 之后的 7，所以我们得到：

7   4 | 2   3   9   1                   7
                                       /
                                      4

在伪代码循环的第二次迭代中，我们调用Heap-Insert(A, 2)，所以Heap-Insert执行它的第一步：

7   4   2 | 3   9   1                   7
                                       / \
                                      4   2

...并发现在执行第 2 步和第 3 步时无需更改任何内容。

我们继续插入3：

7   4   2   3 | 9   1                   7
                                       / \
                                      4   2
                                     /
                                    3

...再次无需更改，因为 3 小于 4（请记住 A[2] 是 A[4] 的父级。

我们继续插入9：

7   4   2   3   9 | 1                   7
                                       / \
                                      4   2
                                     / \
                                    3   9

这里9 > 4，还有9 > 7，所以Heap-Insert将A进一步修改为：

9   7   2   3   4 | 1                   9
                                       / \
                                      7   2
                                     / \
                                    3   4

还有一个：

9   7   2   3   4   1                   9
                                      /   \
                                     7     2
                                    / \   /
                                   3   4 1

与 Heap-Insert 无关，因为 1 < 2。

用于构建堆的改进算法

Modified algorithm for building a Heap

algorithm

heap