堆的核心操作

为确保堆在修改后仍保持其定义属性（最小堆或最大堆），我们需要高效的操作来添加元素、移除优先级最高的元素（根节点），以及从初始元素集合构建堆。这些主要操作包括插入、提取（最小或最大）和建堆。它们通过在树结构中向上或向下移动元素来恢复堆的属性。

下面我们以最小堆为例，说明这些操作的工作方式。最大堆的逻辑与此类似，只是比较标准相反（寻找最大元素而非最小元素）。

插入元素

向堆中添加新元素时，我们必须确保两点：结构保持为一个完全二叉树，以及堆的属性得到维护。

1. 维护结构：将新元素添加到树最低层的第一个可用位置。在常见的数组表示中，这只需将元素添加到数组末尾即可。
2. 恢复堆属性（上浮）：新添加的元素可能破坏堆属性。将新元素与其父节点比较。如果它小于父节点（在最小堆中），则交换它们。重复此比较和潜在的交换过程，将元素在树中向上移动（朝向根节点），直到它大于或等于其父节点，或成为新的根节点。这个过程通常称为“上浮”或“冒泡上浮”。

考虑将值8插入到以下最小堆中：

插入前的初始最小堆。

首先，将8添加到下一个可用位置：

将8添加到下一个可用位置（作为30的子节点）。

现在，上浮8：

• 将8与其父节点30比较。因为$8 < 30$，交换它们。
• 将8与其新父节点20比较。因为$8 < 20$，交换它们。
• 将8与其新父节点10比较。因为$8 < 10$，交换它们。
• 8现在是根节点，所以过程停止。

插入8并执行上浮后的最终最小堆。

插入操作的时间复杂度主要由上浮过程决定。由于一个包含$n$元素的完全二叉树的高度为$O(\log n)$，因此所需的最大交换次数与高度成比例。所以，插入操作的时间复杂度为$O(\log n)$。

提取最小/最大元素

在最小堆中，最小元素总是在根节点。类似地，最大元素在最大堆的根节点。提取这个元素需要移除根节点，然后恢复堆的属性。我们来看看提取最小操作：

1. 保存根节点：保存根节点的值（最小值）以便返回。
2. 维护结构：将堆中最后一个元素（最低层最右边的元素）移动到根节点位置。这保持了树的完整性。
3. 恢复堆属性（下沉）：现在位于根节点的元素可能大于其子节点，从而违反了最小堆属性。将新根节点与其子节点比较。如果它大于任一子节点，则与两个子节点中较小的一个交换。重复此比较和交换过程，将元素在树中向下移动，直到它小于或等于其所有子节点，或成为叶节点。这被称为“下沉”或“冒泡下沉”。

我们从刚才创建的堆中提取最小元素（8）：

确定要提取的根节点（8）和最后一个元素（30）。

移除8，将30移到根节点：

用最后一个元素（30）替换根节点。

现在，下沉30：

• 将30与其子节点10和15比较。较小的子节点是10。因为$30 > 10$，交换30与10。
• 30现在是10的子节点。将30与其新子节点20和25比较。较小的子节点是20。因为$30 > 20$，交换30与20。
• 30现在是20的子节点。它没有子节点，所以它是一个叶节点。下沉过程停止。

提取原始最小值并执行下沉后的最终最小堆。

与插入类似，提取操作的时间复杂度主要由下沉过程决定，该过程涉及从根节点到叶节点的路径遍历。这条路径的长度为$O(\log n)$，因此提取操作也需要$O(\log n)$时间。

构建堆（建堆）

通常，我们从一个未排序的元素集合开始，希望构建一个包含所有这些元素的堆。我们可以使用上面描述的插入操作一个接一个地插入每个元素。由于有$n$个元素，每次插入需要$O(\log n)$时间，因此这种方法总共需要$O(n \log n)$时间。

然而，存在一种更高效的方法，通常称为建堆或弗洛伊德算法。它的工作原理是从树中最后一个非叶节点开始，对其应用下沉操作。然后，它向后遍历数组（或在树中向上），对每个节点应用下沉操作，直到到达根节点。

为什么从最后一个非叶节点开始？因为所有叶节点都已经是大小为1的有效堆。通过逐步向上应用下沉操作，我们确保当我们处理一个节点时，其子节点已经是有效子堆的根节点。

我们来将数组[30, 20, 15, 10, 25, 18, 17]建为最小堆。 对应的树结构初始如下所示（显示了索引）：

       30 (0)
      /    \
    20(1)  15(2)
   /   \   /   \
 10(3) 25(4) 18(5) 17(6)

最后一个非叶节点位于索引2（值为15）。索引范围是：floor(n/2) - 1到0。这里$n=7$，所以索引是2, 1, 0。

1. 下沉索引2处的节点（15）：子节点是18和17。较小的子节点是17。因为$15 < 17$，无需交换。
2. 下沉索引1处的节点（20）：子节点是10和25。较小的子节点是10。因为$20 > 10$，交换20和10。20现在位于索引3（叶节点），所以下沉停止。

          30 (0)
         /    \
       10(1)  15(2)  <- 20和10已交换
      /   \   /   \
    20(3) 25(4) 18(5) 17(6)
   

3. 下沉索引0处的节点（30）：子节点是10和15。较小的子节点是10。因为$30 > 10$，交换30与10。

          10 (0)  <- 30和10已交换
         /    \
       30(1)  15(2)
      /   \   /   \
    20(3) 25(4) 18(5) 17(6)
   

   现在30位于索引1。将30与其子节点20和25比较。较小的子节点是20。因为$30 > 20$，交换30与20。

          10 (0)
         /    \
       20(1)  15(2) <- 30和20已交换
      /   \   /   \
    30(3) 25(4) 18(5) 17(6)
   

   30现在位于索引3（叶节点），所以下沉停止。

最终建堆后的数组是[10, 20, 15, 30, 25, 18, 17]。

应用高效的建堆算法后最小堆的结构。

尽管它涉及到大约$n/2$次的下沉操作（一个$O(\log n)$的操作），但更仔细的分析表明，建堆算法的总工作量实际上是$O(n)$。这是因为大多数节点都靠近树的底部，并且对于靠近叶子的节点，下沉操作运行得更快。对于大型集合，使用这种自底向上的方法构建堆比重复插入要快得多。

这些核心操作，包括插入和提取的对数时间复杂度以及初始构建的线性时间，使得堆在管理具有优先级的元素方面效率很高，并为优先级队列提供了支撑。