在 PHP 中实现二进制堆

使用数组是实现二进制堆最常用的方法之一。由于堆是完整的二叉树，因此使用数组可以轻松实现。如果我们认为根项位于索引 1，那么子项将位于索引 2 和 3。我们可以用 i 表示根项，2*i 表示左侧子项，2*i +1 表示右侧子项。此外，我们将以均值堆为例进行说明。因此，让我们从最小堆实现的类结构开始。

首先，我们将为 MinHeap 创建一个类，该类将有两个属性，一个用于存储堆数组，另一个用于计算任何给定时刻堆中元素的数量。下面是该类的代码：

如果我们看一下前面的代码，就会发现我们已经将堆数组初始化为从 0 索引到 $size + 1 的所有 0 值。由于我们考虑将根放在索引 1 处，因此需要一个多出一个空格的数组。现在，我们需要一种从给定数组中构建堆的方法。由于我们必须满足堆属性，因此必须向堆中添加一个项目，并使用 C 语言步骤检查堆属性是否满足。下面是通过一次插入一个项目来创建堆的代码块，以及 siftUp 过程：

首先，我们使用 create 方法从数组中创建一个堆。对于数组中的每个元素，我们使用 insert 方法将其插入堆。在 insert 方法中，我们会检查堆的当前大小是否为 0。如果当前大小为 0，我们会将第一个项目添加到索引 1，并将下一个计数器设置为 2。 如果堆中已经有一个项目，我们会将新项目存储到最后一个位置，并递增计数器。我们还会调用 siftUp() 方法，以确保新插入的值满足堆属性。

在 siftUp 方法中，我们将最后一个位置与其父位置进行比较。如果子代值小于父代值，我们就交换它们。我们将继续这样做，直到到达顶部的根节点。这种方法可以确保，如果最后插入的值最小，它就会在树中被向上筛选。但如果不是，树将保持原样。虽然我们已经谈到了交换，但还没有看到实现方法。下面就是实现方法：

由于根元素在堆中具有最小值（我们正在实现 minheap）。extract 方法将一直返回当前堆的最小值：

extractMin 方法返回数组的第一个索引，并将其替换为数组的最后一项。之后，它会对新放置的根值执行 siftDown 检查，以确保堆属性。由于我们提取的是根值，因此将最后一个索引值替换为 0，用于初始化堆数组。现在，我们将编写 siftDown 方法，并调用 extract 方法：

我们认为位于索引 $k 的项目是最小值。然后，我们将最小值与左右子节点进行比较。如果有更小的值，我们就将最小值与根节点交换，直到树满足堆属性为止。每次需要交换时，该函数都会递归调用自身。现在，我们还需要一个方法来将当前堆显示为字符串。为此，我们可以编写一个如下的小方法：

如果我们现在把所有部分都整合在一起，我们就有了一个可靠的最小堆实现。现在让我们运行一个测试，看看我们的实现是否满足最小堆属性。我们可以运行以下代码来构建堆，并多次从堆中提取最小值：

如果我们运行此代码，终端中将显示以下输出：

从前面的输出中我们可以看到，当我们构建最小堆时，最小值 9 位于堆根。然后我们提取了最小值，从堆中取出了 9。然后，根部被下一个最小值 26 占用，接着是 34、37、44 和 65。每取出一个最小值，堆就会重新构建一个最小值。既然我们已经了解了堆数据结构的所有适用操作，现在我们来分析一下不同堆操作的复杂性。