最小堆（Min Heap）的性质与基本操作
字数 2944 2025-12-05 08:31:00

最小堆（Min Heap）的性质与基本操作

最小堆（Min Heap）是一种特殊的完全二叉树数据结构，它满足“堆性质”：对于堆中任意一个非根节点，其值总是大于或等于其父节点的值。这意味着堆的根节点是整个堆中的最小元素。最小堆常用于实现优先队列，支持高效地插入新元素、删除最小元素等操作。

1. 最小堆的结构性质

  • 完全二叉树：最小堆在物理结构上通常使用数组来实现，逻辑上是一棵完全二叉树。这意味着除了最后一层，其他层都是满的，且最后一层的节点尽可能靠左排列。
  • 数组表示：给定一个节点在数组中的索引 i（通常从0开始）：
    • 其父节点的索引为 (i - 1) / 2（向下取整）。
    • 其左子节点的索引为 2 * i + 1。
    • 其右子节点的索引为 2 * i + 2。
  • 堆性质（最小堆）：对于任意节点 i，有 array[parent(i)] ≤ array[i]。根节点（array[0]）是全局最小值。

2. 核心操作详解

2.1 向上调整（Percolate Up / Sift Up）

当在堆的末尾（数组尾部）插入一个新元素，或当某个节点的值被减小时，可能会破坏堆性质。向上调整的目标是将这个节点向上移动，直到堆性质恢复。

步骤：

  1. 从目标节点（比如新插入的节点）开始，设其索引为 current。
  2. 计算其父节点索引 parent = (current - 1) / 2。
  3. 循环比较 array[current] 和 array[parent]：
    a. 如果 array[current] >= array[parent]，说明从当前节点到根节点已满足堆性质，调整结束。
    b. 如果 array[current] < array[parent]，则违反了最小堆性质。交换 array[current] 和 array[parent] 的值。
    c. 将 current 移动到 parent 的位置（即 current = parent），然后重复步骤3，直到 current 成为根节点（current == 0）或条件a满足。

时间复杂度：O(log n)，其中n是堆中元素个数，因为调整路径的长度等于树的高度。

2.2 向下调整（Percolate Down / Heapify / Sift Down）

当移除堆顶的最小元素（或替换堆顶元素为一个更大的值）时，通常会将堆的最后一个元素移到堆顶。此时，堆顶可能不满足堆性质。向下调整的目标是将这个节点向下移动，直到堆性质恢复。

步骤：

  1. 从目标节点（比如新的堆顶元素）开始，设其索引为 current。
  2. 找出 current 节点的两个子节点中值较小的那一个。设其索引为 minChild。
    • 左子节点索引：left = 2 * current + 1
    • 右子节点索引：right = 2 * current + 2
    • 如果 left 已越界（即left >= heapSize），说明 current 是叶子节点，调整结束。
    • 否则，比较 array[left] 和 array[right]（如果 right 未越界），将值较小的那个索引赋给 minChild。
  3. 循环检查：
    a. 如果 current 是叶子节点，或者 array[current] <= array[minChild]，说明从当前节点向下的子树已满足堆性质，调整结束。
    b. 如果 array[current] > array[minChild]，则违反了最小堆性质。交换 array[current] 和 array[minChild] 的值。
    c. 将 current 移动到 minChild 的位置（即 current = minChild），然后重复步骤2和3，直到条件a满足。

时间复杂度：O(log n)。

3. 基于核心操作构建堆的基本功能

3.1 插入元素（Insert）

  1. 将新元素追加到数组的末尾。此时，堆的大小增加了1，并且新元素可能比它的父节点小，从而破坏了堆性质。
  2. 对新插入的这个节点（即数组的最后一个索引位置）执行一次向上调整（Sift Up） 操作，以恢复堆性质。

3.2 获取最小元素（Find-Min）

由于最小堆的性质，堆顶（数组的第一个元素 array[0]）就是最小元素。此操作的时间复杂度是 O(1)。

3.3 删除最小元素（Extract-Min / Delete-Min）

这是最小堆的关键操作。

  1. 记录堆顶元素 array[0]，它就是我们要返回的最小值。
  2. 将数组的最后一个元素移到堆顶，即 array[0] = array[heapSize - 1]。
  3. 将堆的大小减1（heapSize--），相当于从逻辑上移除了最后一个位置。
  4. 对新的堆顶节点（索引0） 执行一次向下调整（Sift Down） 操作，以恢复堆性质。
  5. 返回第一步记录的最小值。

3.4 构建堆（Build-Heap）

给定一个无序的数组，如何高效地将其构建成一个合法的堆？一个直观但低效的方法是反复调用 Insert 操作，时间复杂度为 O(n log n)。

更高效的方法是自底向上的向下调整：

  1. 将这个无序数组看作一个完全二叉树。
  2. 从最后一个非叶子节点开始，向前遍历到根节点。最后一个非叶子节点的索引是 (heapSize / 2) - 1。
  3. 对遍历到的每一个节点，都执行一次向下调整（Sift Down） 操作。

为什么是最后一个非叶子节点？ 因为叶子节点本身已经是合法的堆（只有一个节点），不需要调整。
为什么有效？ 这个方法的妙处在于，当对一个节点进行调整时，它的左右子树都已经是合法的堆了（因为我们是从后向前调整的）。这个算法的时间复杂度是 O(n)，而不是 O(n log n)。

4. 总结与示例

最小堆的核心在于其结构性质（完全二叉树）和堆性质（父节点值 ≤ 子节点值）。
向上调整（Sift Up） 用于在节点值变小时（如插入后）恢复堆性质，方向是从下到上。
向下调整（Sift Down） 用于在节点值变大时（如删除堆顶后）恢复堆性质，方向是从上到下。

示例：插入元素 3
假设现有最小堆 [5, 10, 7, 12, 15]。

  1. 插入3到末尾：[5, 10, 7, 12, 15, 3]。
  2. 对索引5（值为3）进行Sift Up：
    • 父节点索引 (5-1)/2=2，值为7。3<7，交换：[5, 10, 3, 12, 15, 7]。
    • 当前节点索引变为2，父节点索引 (2-1)/2=0，值为5。3<5，交换：[3, 10, 5, 12, 15, 7]。
    • 当前节点索引变为0，已是根节点，调整结束。新的堆是 [3, 10, 5, 12, 15, 7]。

理解并掌握了向上和向下这两个核心的调整操作，你就掌握了最小堆（以及最大堆）所有基本操作的精髓。

最小堆（Min Heap）的性质与基本操作 最小堆（Min Heap）是一种特殊的完全二叉树数据结构，它满足“堆性质”：对于堆中任意一个非根节点，其值总是大于或等于其父节点的值。这意味着堆的根节点是整个堆中的最小元素。最小堆常用于实现优先队列，支持高效地插入新元素、删除最小元素等操作。 1. 最小堆的结构性质 完全二叉树 ：最小堆在物理结构上通常使用数组来实现，逻辑上是一棵完全二叉树。这意味着除了最后一层，其他层都是满的，且最后一层的节点尽可能靠左排列。 数组表示 ：给定一个节点在数组中的索引 i （通常从0开始）： 其父节点的索引为 (i - 1) / 2 （向下取整）。 其左子节点的索引为 2 * i + 1 。 其右子节点的索引为 2 * i + 2 。 堆性质（最小堆） ：对于任意节点 i ，有 array[parent(i)] ≤ array[i] 。根节点（ array[0] ）是全局最小值。 2. 核心操作详解 2.1 向上调整（Percolate Up / Sift Up） 当在堆的末尾（数组尾部）插入一个新元素，或当某个节点的值被 减小 时，可能会破坏堆性质。向上调整的目标是将这个节点向上移动，直到堆性质恢复。 步骤 ： 从目标节点（比如新插入的节点）开始，设其索引为 current 。 计算其父节点索引 parent = (current - 1) / 2 。 循环比较 array[current] 和 array[parent] ： a. 如果 array[current] >= array[parent] ，说明从当前节点到根节点已满足堆性质，调整结束。 b. 如果 array[current] < array[parent] ，则违反了最小堆性质。交换 array[current] 和 array[parent] 的值。 c. 将 current 移动到 parent 的位置（即 current = parent ），然后重复步骤3，直到 current 成为根节点（ current == 0 ）或条件a满足。 时间复杂度 ：O(log n)，其中n是堆中元素个数，因为调整路径的长度等于树的高度。 2.2 向下调整（Percolate Down / Heapify / Sift Down） 当移除堆顶的最小元素（或替换堆顶元素为一个更大的值）时，通常会将堆的最后一个元素移到堆顶。此时，堆顶可能不满足堆性质。向下调整的目标是将这个节点向下移动，直到堆性质恢复。 步骤 ： 从目标节点（比如新的堆顶元素）开始，设其索引为 current 。 找出 current 节点的 两个子节点中值较小的那一个 。设其索引为 minChild 。 左子节点索引： left = 2 * current + 1 右子节点索引： right = 2 * current + 2 如果 left 已越界（即 left >= heapSize ），说明 current 是叶子节点，调整结束。 否则，比较 array[left] 和 array[right] （如果 right 未越界），将值较小的那个索引赋给 minChild 。 循环检查： a. 如果 current 是叶子节点，或者 array[current] <= array[minChild] ，说明从当前节点向下的子树已满足堆性质，调整结束。 b. 如果 array[current] > array[minChild] ，则违反了最小堆性质。交换 array[current] 和 array[minChild] 的值。 c. 将 current 移动到 minChild 的位置（即 current = minChild ），然后重复步骤2和3，直到条件a满足。 时间复杂度 ：O(log n)。 3. 基于核心操作构建堆的基本功能 3.1 插入元素（Insert） 将新元素 追加 到数组的末尾。此时，堆的大小增加了1，并且新元素可能比它的父节点小，从而破坏了堆性质。 对 新插入的这个节点 （即数组的最后一个索引位置）执行一次 向上调整（Sift Up） 操作，以恢复堆性质。 3.2 获取最小元素（Find-Min） 由于最小堆的性质，堆顶（数组的第一个元素 array[0] ）就是最小元素。此操作的时间复杂度是 O(1)。 3.3 删除最小元素（Extract-Min / Delete-Min） 这是最小堆的关键操作。 记录堆顶元素 array[0] ，它就是我们要返回的最小值。 将数组的 最后一个元素 移到堆顶，即 array[0] = array[heapSize - 1] 。 将堆的大小减1（ heapSize-- ），相当于从逻辑上移除了最后一个位置。 对 新的堆顶节点（索引0） 执行一次 向下调整（Sift Down） 操作，以恢复堆性质。 返回第一步记录的最小值。 3.4 构建堆（Build-Heap） 给定一个无序的数组，如何高效地将其构建成一个合法的堆？一个直观但低效的方法是反复调用 Insert 操作，时间复杂度为 O(n log n)。 更高效的方法是 自底向上的向下调整 ： 将这个无序数组看作一个完全二叉树。 从 最后一个非叶子节点 开始，向前遍历到根节点。最后一个非叶子节点的索引是 (heapSize / 2) - 1 。 对遍历到的 每一个节点 ，都执行一次 向下调整（Sift Down） 操作。 为什么是最后一个非叶子节点？ 因为叶子节点本身已经是合法的堆（只有一个节点），不需要调整。 为什么有效？ 这个方法的妙处在于，当对一个节点进行调整时，它的左右子树都已经是合法的堆了（因为我们是从后向前调整的）。这个算法的时间复杂度是 O(n)，而不是 O(n log n)。 4. 总结与示例 最小堆的核心 在于其结构性质（完全二叉树）和堆性质（父节点值 ≤ 子节点值）。 向上调整（Sift Up） 用于在节点值 变小 时（如插入后）恢复堆性质，方向是 从下到上 。 向下调整（Sift Down） 用于在节点值 变大 时（如删除堆顶后）恢复堆性质，方向是 从上到下 。 示例：插入元素 3 假设现有最小堆 [5, 10, 7, 12, 15] 。 插入3到末尾： [5, 10, 7, 12, 15, 3] 。 对索引5（值为3）进行Sift Up： 父节点索引 (5-1)/2=2 ，值为7。3<7，交换： [5, 10, 3, 12, 15, 7] 。 当前节点索引变为2，父节点索引 (2-1)/2=0 ，值为5。3<5，交换： [3, 10, 5, 12, 15, 7] 。 当前节点索引变为0，已是根节点，调整结束。新的堆是 [3, 10, 5, 12, 15, 7] 。 理解并掌握了向上和向下这两个核心的调整操作，你就掌握了最小堆（以及最大堆）所有基本操作的精髓。