堆操作

我们曾多次提到，堆是一种特殊的树形数据结构，因此我们必须确保首先从给定的项列表中构建一个堆。由于堆具有严格的堆属性，我们必须在每一步都满足堆属性。下面是堆的一些核心操作：

  • 创建堆

  • 插入新值

  • 从堆中提取最小值或最大值

  • 删除一个值

  • 交换

从给定的项目或数字列表创建堆时，我们需要确保同时满足堆属性和二叉树属性。这意味着父节点必须大于或小于子节点，而且树中的所有节点都必须如此。此外，树必须始终是一棵完整的二叉树。创建堆时，我们从一个节点开始，然后向堆中插入一个新节点。

插入节点操作有一组确定的步骤。我们不能从任意节点开始。插入操作的步骤如下：

  1. 在堆的底部插入新节点。

  2. 检查新节点与父节点值的顺序是否正确。如果顺序正确，就到此为止。

  3. 如果顺序不对，则对调它们，然后转到上一步，检查新对调节点与其父节点。这一步和上一步被称为 "向上筛" 或 "向上堆" 或 "向上冒泡" 或 "向上堆" 等。

提取操作（最小值或最大值）会从堆中取出根节点。之后，我们必须执行以下操作，以确保剩余堆的堆属性：

  1. 移动堆中的最后一个节点作为新的根节点。

  2. 将新根节点与子节点进行比较，如果顺序正确，则停止。

  3. 如果不对，则交换根节点和子节点（对于 MinHeap，交换最小的子节点；对于 MaxHeap，交换最大的子节点），然后继续上一步。这一步和上一步被称为 sift down 或 down-heap，或 bubbledown 或 heapify-down，等等。

在堆中，重要的操作之一就是交换。在许多情况下，我们必须在不影响树属性的情况下交换两个节点的两个值。现在我们将使用 PHP 7 来实现二进制堆。