Min-Heap 中 decrease-key 操作的实现

1. 概述

在本教程中，我们将介绍基于最小堆（Min-Heap）的优先队列中 decrease-key 操作的实现。

首先，我们回顾一下 min-heap 的基本概念与结构。接着，我们会对插入和提取操作进行必要的扩展，以便支持 decrease-key。最后，我们将完整实现该操作。

decrease-key 主要用于像 Dijkstra 算法这种需要动态调整节点权重的场景。当发现更短路径时，我们需要将节点的权重降低并重新调整堆结构。

---

2. Min-Heap 背景知识

2.1. Min-Heap 的用途

Min-Heap 是一种常用于实现优先队列的数据结构，支持以下两种操作：

• ✅ 插入新元素（Insert）：时间复杂度为 O(log n)。
• ✅ 提取最小值（Extract Min）：时间复杂度也为 O(log n)。

其中 n 表示堆中当前的元素数量。

本教程中，我们将新增一个操作：

• ✅ decrease-key：用于降低某个节点的值，并维护堆结构。

2.2. Min-Heap 的结构

Min-Heap 是一个完全二叉树，满足以下性质：

• 每个节点的值小于或等于其子节点的值。
• 最小值始终位于根节点。

堆通常用数组实现，结构如下：

• 根节点位于索引 1。
• 节点 i 的左子节点位于 2i，右子节点位于 2i + 1。
• 节点 i 的父节点位于 i / 2（向下取整）。

如下图所示为一个典型的 min-heap 示例：

对应的数组存储如下：

---

3. 基本操作的扩展

为了支持 decrease-key，我们需要能快速定位堆中任意元素的位置。为此，我们在堆结构中引入一个 map 来记录每个元素在数组中的索引。

3.1. Swap 操作

每次插入、提取或更新节点时，都需要交换元素位置。我们实现一个 swap 方法，用于交换两个索引位置的元素，并更新 map。

void swap(int[] A, int i, int j, Map<Integer, Integer> map) {
    int temp = A[i];
    A[i] = A[j];
    A[j] = temp;

    map.put(A[i], i);
    map.put(A[j], j);
}

✅ 时间复杂度：O(1)

3.2. 插入操作（Insert）

插入新元素时，将其放在数组末尾，然后不断向上调整直到满足堆性质。

void insert(int[] A, int n, int key, Map<Integer, Integer> map) {
    n++;
    A[n] = key;
    map.put(key, n);
    int i = n;

    while (i > 1) {
        if (A[i] < A[i / 2]) {
            swap(A, i, i / 2, map);
            i = i / 2;
        } else {
            break;
        }
    }
}

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

3.3. 提取最小值操作（Extract Min）

提取最小值后，将最后一个元素移到根节点，并不断向下调整。

int extractMin(int[] A, int n, Map<Integer, Integer> map) {
    int answer = A[1];
    map.remove(answer);

    A[1] = A[n];
    map.put(A[1], 1);
    n--;

    int i = 1;
    while (2 * i <= n) {
        int left = 2 * i;
        int right = 2 * i + 1;

        int smallest = left;
        if (right <= n && A[right] < A[left]) {
            smallest = right;
        }

        if (A[i] > A[smallest]) {
            swap(A, i, smallest, map);
            i = smallest;
        } else {
            break;
        }
    }

    return answer;
}

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

---

4. Decrease-Key 操作

实现 decrease-key 的核心步骤如下：

1. ✅ 通过 map 找到目标元素的索引；
2. ✅ 更新其值；
3. ✅ 向上调整堆结构以维持堆性质。

void decreaseKey(int[] A, int key, int subtract, Map<Integer, Integer> map) {
    int i = map.get(key);
    map.remove(key);
    A[i] -= subtract;
    map.put(A[i], i);

    while (i > 1) {
        if (A[i] < A[i / 2]) {
            swap(A, i, i / 2, map);
            i = i / 2;
        } else {
            break;
        }
    }
}

⚠️ 注意：

• 该操作只能用于将值 减小，不能用于增大值；
• 如果增大值，应该使用 increase-key 并向下调整。

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

---

5. 总结

本文我们介绍了如何在 min-heap 中实现 decrease-key 操作。关键点包括：

• ✅ 引入 map 来记录元素索引；
• ✅ 修改插入和提取操作以维护 map；
• ✅ 实现 decrease-key 并向上调整堆结构；
• ✅ 时间复杂度均为 O(log n)。

这个操作在图算法（如 Dijkstra）中非常关键，能显著提升性能。掌握其实现原理，有助于深入理解堆结构和优先队列的应用场景。