深入理解Java堆数据结构（从零开始掌握最大堆、最小堆与优先队列实现）

由于堆是完全二叉树，我们可以使用数组高效地存储它。对于数组中索引为 i 的元素：

• 父节点索引： (i - 1) / 2
• 左子节点索引： 2 * i + 1
• 右子节点索引： 2 * i + 2

为什么需要堆？

堆的核心优势在于它能在 O(log n) 时间内完成插入和删除操作，并在 O(1) 时间内获取最大值（最大堆）或最小值（最小堆）。这使得堆非常适合用于：

• 任务调度系统（优先级高的任务先执行）
• Top-K 问题（如找出最大的10个数）
• 堆排序算法（一种高效的排序方法）
• 图算法中的 Dijkstra 最短路径

Java 中如何实现堆？

虽然 Java 标准库提供了 PriorityQueue 类（默认是最小堆），但为了深入理解原理，我们手动实现一个最小堆。

最小堆的 Java 实现

import java.util.ArrayList;import java.util.List;public class MinHeap {    private List<Integer> heap;    public MinHeap() {        heap = new ArrayList<>();    }    // 获取父节点索引    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;    }    // 插入元素    public void insert(int value) {        heap.add(value);        heapifyUp(heap.size() - 1);    }    // 自底向上调整堆    private void heapifyUp(int i) {        if (i > 0 && heap.get(i) < heap.get(parent(i))) {            swap(i, parent(i));            heapifyUp(parent(i));        }    }    // 删除堆顶元素（最小值）    public int extractMin() {        if (heap.isEmpty()) {            throw new RuntimeException("Heap is empty!");        }        int min = heap.get(0);        heap.set(0, heap.get(heap.size() - 1));        heap.remove(heap.size() - 1);        heapifyDown(0);        return min;    }    // 自顶向下调整堆    private void heapifyDown(int i) {        int smallest = i;        int left = leftChild(i);        int right = rightChild(i);        if (left < heap.size() && heap.get(left) < heap.get(smallest)) {            smallest = left;        }        if (right < heap.size() && heap.get(right) < heap.get(smallest)) {            smallest = right;        }        if (smallest != i) {            swap(i, smallest);            heapifyDown(smallest);        }    }    // 交换两个元素    private void swap(int i, int j) {        int temp = heap.get(i);        heap.set(i, heap.get(j));        heap.set(j, temp);    }    // 打印堆（用于调试）    public void printHeap() {        System.out.println(heap);    }}

使用示例

public class Main {    public static void main(String[] args) {        MinHeap minHeap = new MinHeap();        minHeap.insert(10);        minHeap.insert(5);        minHeap.insert(20);        minHeap.insert(3);        minHeap.printHeap(); // 输出: [3, 5, 20, 10]        System.out.println("最小值: " + minHeap.extractMin()); // 输出: 3        minHeap.printHeap(); // 输出: [5, 10, 20]    }}

Java 内置的 PriorityQueue

Java 提供了 java.util.PriorityQueue，它底层就是用堆实现的。默认是最小堆，也可以通过自定义比较器实现最大堆：

// 最小堆（默认）PriorityQueue<Integer> minHeap = new PriorityQueue<>();// 最大堆PriorityQueue<Integer> maxHeap = new PriorityQueue<>((a, b) -> b - a);// 或者使用 Collections.reverseOrder()PriorityQueue<Integer> maxHeap2 = new PriorityQueue<>(Collections.reverseOrder());

总结

通过本教程，你已经掌握了 Java堆数据结构 的基本概念、手动实现方式以及 Java 内置工具类的使用。无论是面试高频考点的 堆排序算法，还是工程中常见的 优先队列实现，堆都是不可或缺的数据结构。

记住：最大堆适合快速获取最大值，最小堆适合快速获取最小值。合理选择堆的类型，能让你的程序更高效！

希望这篇教程对你有帮助！如果你有任何疑问，欢迎在评论区留言交流。