一种改进的堆生成算法

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开始，然后简单地将从A2到A.length的所有值添加到堆中，而不实际构建最大堆吗？

我不明白除了限制堆的总大小之外，heap-size = 1是如何在算法中做任何事情的。我对你如何建立一个最大的堆感到困惑。

从书中所述的情况来看，正常的最大堆首先将每个数组值插入堆中，然后从A/2位置开始，然后向后工作，然后交换比调用Max-Heapify计算的当前值更大的值。

那么，既然没有Max-Heapify(A, largest)调用，但是只有一个heap-insert(A, A[i])，那么这个最大堆将如何工作呢？

Answer 1

首先，这个问题与堆排序无关，堆排序只是堆的应用程序之一。您在询问堆结构的情况。

您提供的伪代码确实是构建堆的另一种方法(而且效率较低)，这实际上是许多人在不知道Floyd标准算法时会提出的算法。

所以看一看代码：

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

这个算法的大部分逻辑都是在Heap-Insert函数中进行的，它不仅仅是一个简单的“附加”数组:它所做的远不止这些。维基百科将该隐藏算法描述如下：

1. 将元素添加到堆最左边的打开空间的底部。
2. 将添加的元素与其父元素进行比较；如果它们的顺序正确，则停止。
3. 如果没有，则与其父元素交换并返回到前一步。

你在你的问题中写道：

没有最大值(A，最大)

实际上，如果在使用堆之前已经知道最大值是什么，那就太简单了。您需要首先在堆中插入一个值(任何值)，并让堆执行它的魔术(在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

...and发现，在执行步骤2和步骤3时，没有什么需要更改。

我们继续插入3条：

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

...and同样不需要更改，因为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

当1< 2时，Heap-Insert没有什么可做的了。