【数据结构】进阶大厂必备：彻底搞懂堆（Heap）的结构、堆排序及优先队列实现

例如，上面最小堆的数组表示为：[5, 8, 9, 12, 11]。下标 0 是根节点 5，下标 1 是 8，下标 2 是 9，下标 3 是 12，下标 4 是 11。验证一下：下标 1 的父节点是 (1-1)/2 = 0，确实指向 5；下标 1 的左子节点是 2*1+1 = 3，指向 12，右子节点是 4，指向 11，符合树的结构。

这种存储方式既节省空间，又方便通过下标快速访问父子节点。

3. 堆的基本操作

堆的核心操作是插入和删除堆顶元素，它们都需要通过上浮和下沉来维持堆序性质。

3.1 插入元素（上浮）

向堆中插入一个新元素时，我们先将它放在数组的末尾（保证完全二叉树结构），然后让它上浮到合适的位置。

上浮过程：比较当前节点与父节点的值，如果违反堆序（在最小堆中，当前节点小于父节点），则交换它们，然后继续向上比较，直到满足条件或到达根节点。

示例：向上面最小堆插入元素 3。

初始堆：[5, 8, 9, 12, 11]，末尾添加 3 后：[5, 8, 9, 12, 11, 3]。

3 的下标是 5，父节点下标 (5-1)/2 = 2，值为 9。3 < 9，交换 → [5, 8, 3, 12, 11, 9]。

现在 3 在位置 2，父节点下标 (2-1)/2 = 0，值为 5。3 < 5，交换 → [3, 8, 5, 12, 11, 9]。

到达根节点，上浮结束。最终堆顶是最小值 3。

3.2 删除堆顶元素（下沉）

删除堆顶元素（即弹出最小值）时，我们先将数组最后一个元素移到堆顶，然后让这个元素下沉到合适位置。

下沉过程：比较当前节点与左右子节点中较小的那个（最小堆），如果当前节点大于那个较小的子节点，则交换，然后继续向下比较，直到满足条件或到达叶子节点。

示例：从上面最终堆 [3, 8, 5, 12, 11, 9] 删除堆顶。

将最后一个元素 9 移到堆顶：[9, 8, 5, 12, 11]（数组长度减 1）。

当前节点 9（下标 0），左子 8（下标 1），右子 5（下标 2）。较小的是 5（因为 5 < 8），9 > 5，交换 → [5, 8, 9, 12, 11]。

现在 9 在位置 2，左子下标 5（已超出），下沉结束。最终堆为 [5, 8, 9, 12, 11]。

注意：删除操作通常只删除堆顶元素，因为堆主要用来快速获取最值。如果要删除任意元素，可以先用该元素与堆顶交换，再删除堆顶，但一般不常用。

3.3 建堆

如果给我们一个无序数组，如何将其构建成堆？有两种方法：

自上而下上浮：从空堆开始，依次插入每个元素（调用上浮）。时间复杂度 O(n log n)。
自下而上下沉（Floyd 算法）：从最后一个非叶子节点开始，依次对每个节点执行下沉操作。时间复杂度 O(n)，更高效。

最后一个非叶子节点的下标为 n/2 - 1（整数除法）。为什么？因为最后一个节点的下标是 n-1，其父节点即为最后一个非叶子节点。

示例：将数组 [4, 10, 3, 5, 1] 构建成最小堆。

n=5，最后一个非叶子节点下标 = 5/2 -1 = 1（值为 10）。

从下标 1 开始下沉：

节点 10（下标1），左子5（下标3），右子1（下标4）。较小的是 1，10 > 1，交换 → [4, 1, 3, 5, 10]。

然后下标 0 下沉：

节点 4（下标0），左子1（下标1），右子3（下标2）。较小的是 1，4 > 1，交换 → [1, 4, 3, 5, 10]。

4 现在在位置1，左子5（下标3），右子10（下标4）。较小的是 5，4 < 5，停止。

建堆完成：[1, 4, 3, 5, 10]。

4. 堆的应用：优先队列

优先队列是一种数据结构，它允许我们以任意顺序插入元素，但每次弹出的都是当前优先级最高（最小或最大）的元素。堆是实现优先队列的最常见方式，因为插入和删除堆顶都是 O(log n) 的时间复杂度。

Java 标准库中的 PriorityQueue 就是基于堆实现的。默认是最小堆，也可以通过传入比较器实现最大堆。

5. 堆排序

堆排序是利用堆进行排序的算法，时间复杂度 O(n log n)，空间复杂度 O(1)（就地排序）。它的步骤如下（以升序排序为例，使用最大堆）：

将无序数组构建成最大堆。

将堆顶元素（最大值）与数组末尾元素交换，此时最大值已就位。

将堆的大小减 1（排除已排序的末尾元素），然后对新的堆顶执行下沉，重新调整成最大堆。

重复步骤 2-3，直到堆的大小为 1。

如果使用最小堆，可以排序成降序。但通常升序用最大堆，降序用最小堆。

示例：对数组 [4, 10, 3, 5, 1] 进行升序堆排序。

建最大堆：[10, 5, 3, 4, 1]

交换 10 和 1：[1, 5, 3, 4, 10]，堆调整前 4 个：下沉 1 → [5, 4, 3, 1, 10]

交换 5 和 1：[1, 4, 3, 5, 10]，堆调整前 3 个：下沉 1 → [4, 1, 3, 5, 10]（1 与 4 交换后，1 在位置 1，子节点 3 和 ... 实际上此时前 3 个是 [4,1,3]，下沉 1 时，与子节点 3 比较，1<3 所以不用动？等等，这里需要仔细）
为避免混淆，我们直接用代码实现。

6. Java 实现最小堆

我们将实现一个简化版的最小堆，支持以下功能：

offer(int val)：插入元素
poll()：删除并返回堆顶
peek()：查看堆顶
size()：返回堆大小
isEmpty()：判空

为了通用性，也可以使用泛型，但这里我们用 int 类型，便于理解。

6.1 最小堆类定义

import java.util.Arrays;
import java.util.NoSuchElementException;

public class MinHeap {
    private int[] array;      // 存储堆元素的数组
    private int size;         // 当前堆中元素个数
    private static final int DEFAULT_CAPACITY = 10;

    public MinHeap() {
        this(DEFAULT_CAPACITY);
    }

    public MinHeap(int capacity) {
        array = new int[capacity];
        size = 0;
    }

    /**
     * 通过一个无序数组构建最小堆（建堆操作）
     */
    public MinHeap(int[] data) {
        // 将数组复制到堆数组中，并扩容
        size = data.length;
        array = Arrays.copyOf(data, Math.max(size, DEFAULT_CAPACITY));
        // 从最后一个非叶子节点开始下沉
        for (int i = (size / 2 - 1); i >= 0; i--) {
            sink(i);
        }
    }

    // 工具方法：获取父节点、左子、右子下标
    private int parent(int i) { return (i - 1) / 2; }
    private int leftChild(int i) { return 2 * i + 1; }
    private int rightChild(int i) { return 2 * i + 2; }

    // 上浮
    private void swim(int k) {
        while (k > 0 && array[parent(k)] > array[k]) {
            swap(k, parent(k));
            k = parent(k);
        }
    }

    // 下沉
    private void sink(int k) {
        while (leftChild(k) < size) { // 至少有一个左子
            int j = leftChild(k);
            // 如果右子存在且小于左子，则指向右子
            if (j + 1 < size && array[j + 1] < array[j]) {
                j = rightChild(k);
            }
            // 如果当前节点小于等于较小子节点，停止下沉
            if (array[k] <= array[j]) {
                break;
            }
            swap(k, j);
            k = j;
        }
    }

    private void swap(int i, int j) {
        int temp = array[i];
        array[i] = array[j];
        array[j] = temp;
    }

    // 插入元素
    public void offer(int val) {
        // 如果数组满了，扩容
        if (size == array.length) {
            array = Arrays.copyOf(array, array.length * 2);
        }
        array[size] = val;
        swim(size);
        size++;
    }

    // 删除并返回堆顶
    public int poll() {
        if (size == 0) {
            throw new NoSuchElementException("堆为空");
        }
        int min = array[0];
        array[0] = array[size - 1];
        size--;
        sink(0);
        return min;
    }

    // 查看堆顶
    public int peek() {
        if (size == 0) {
            throw new NoSuchElementException("堆为空");
        }
        return array[0];
    }

    public int size() {
        return size;
    }

    public boolean isEmpty() {
        return size == 0;
    }

    // 打印堆（用于测试）
    public void print() {
        System.out.print("堆内容: ");
        for (int i = 0; i < size; i++) {
            System.out.print(array[i] + " ");
        }
        System.out.println();
    }
}

6.2 测试最小堆

public class MinHeapTest {
    public static void main(String[] args) {
        // 测试插入
        MinHeap heap = new MinHeap();
        heap.offer(5);
        heap.offer(8);
        heap.offer(9);
        heap.offer(12);
        heap.offer(11);
        heap.offer(3);
        heap.print(); // 预期: 3 8 5 12 11 9 (顺序可能因实现细节不同，但堆性质成立)

        // 测试删除
        System.out.println("poll: " + heap.poll()); // 3
        heap.print(); // 应满足最小堆

        // 测试从数组建堆
        int[] data = {4, 10, 3, 5, 1};
        MinHeap heap2 = new MinHeap(data);
        heap2.print(); // 预期: 1 4 3 5 10

        // 依次弹出所有元素
        while (!heap2.isEmpty()) {
            System.out.print(heap2.poll() + " ");
        }
        // 输出应为升序: 1 3 4 5 10
    }
}

7. 堆排序实现

利用上面的 MinHeap，我们可以轻松实现堆排序：先建堆，然后反复弹出堆顶。这样得到的就是升序序列。

public class HeapSort {
    /**
     * 堆排序（升序），直接修改原数组
     * 思路：使用最小堆，反复弹出堆顶放入新数组，但为了原地排序，通常使用最大堆。
     * 这里为了演示，我们使用最小堆，但需要额外空间。下面给出原地最大堆版本。
     */
    public static void sortAscending(int[] arr) {
        // 构建最大堆
        int n = arr.length;
        // 从最后一个非叶子节点开始下沉，构建最大堆
        for (int i = n / 2 - 1; i >= 0; i--) {
            sinkMax(arr, i, n);
        }
        // 依次将堆顶交换到末尾，并调整堆
        for (int i = n - 1; i > 0; i--) {
            swap(arr, 0, i);          // 堆顶与末尾交换
            sinkMax(arr, 0, i);        // 调整前 i 个元素为最大堆
        }
    }

    // 最大堆下沉（针对数组的一部分）
    private static void sinkMax(int[] arr, int k, int length) {
        while (2 * k + 1 < length) {
            int j = 2 * k + 1; // 左子
            if (j + 1 < length && arr[j + 1] > arr[j]) {
                j = 2 * k + 2; // 右子更大
            }
            if (arr[k] >= arr[j]) {
                break;
            }
            swap(arr, k, j);
            k = j;
        }
    }

    private static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

    public static void main(String[] args) {
        int[] arr = {4, 10, 3, 5, 1};
        System.out.print("排序前: ");
        for (int n : arr) System.out.print(n + " ");
        System.out.println();

        sortAscending(arr);

        System.out.print("排序后: ");
        for (int n : arr) System.out.print(n + " ");
        System.out.println();
    }
}

运行结果：

排序前: 4 10 3 5 1
排序后: 1 3 4 5 10

8. 总结

堆是一种完全二叉树，具有堆序性质，常用数组存储。

最小堆：父节点 ≤ 子节点；最大堆：父节点 ≥ 子节点。

插入：末尾添加，然后上浮。

删除堆顶：末尾元素替换堆顶，然后下沉。

建堆：从最后一个非叶子节点开始下沉，时间复杂度 O(n)。

优先队列是堆的典型应用。

堆排序：利用最大堆进行原地升序排序，步骤为建堆 → 交换堆顶与末尾 → 调整剩余堆

乐奇 Rokid 开放社区

更多推荐

Word Embedding ：从分布式假设到神经网络语言模型

Word Embedding（词嵌入）是一种将离散的词汇符号映射到连续的低维稠密向量空间的技术。在这个向量空间中，语义相似的词在几何距离上彼此接近，从而实现了从"符号匹配"到"语义计算"的跨越。核心定义词嵌入是将单词（或多词短语）表示为固定维度的实值向量，这些向量之间的距离（例如余弦相似度）反映了单词之间的相关性，这种相关性基于单词通常出现的上下文。分布式假设（1954）↓统计共现分析（LSA/S

乐奇 Rokid 开放社区

镜游小导：运行在 Rokid AR 眼镜上的景区实景讲解智能体

项目以 RokidAIUI 开放智能体形态交付：页面用.ink描述，运行在眼镜端智能体运行时，直接调用系统能力。AGENTS.md身份镜游小导v1.0.0，景区 AR 实景讲解智能体；权限（Capabilities）microphonenetworkaudiogyroscope；技能（Skills）。