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

为什么使用数组表示堆？

虽然堆是树形结构，但我们可以用数组高效地表示它。对于索引为 i 的节点：

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

这种映射方式节省了指针空间，同时保持了 O(1) 的父子访问效率。

Java实现最大堆

下面我们用 Java 编写一个简单的最大堆类，支持插入、删除最大值和堆化操作。

import java.util.ArrayList;import java.util.List;public class MaxHeap {    private List<Integer> heap;    public MaxHeap() {        heap = new ArrayList<>();    }    // 获取父节点索引    private int parent(int index) {        return (index - 1) / 2;    }    // 获取左子节点索引    private int leftChild(int index) {        return 2 * index + 1;    }    // 获取右子节点索引    private int rightChild(int index) {        return 2 * index + 2;    }    // 插入元素    public void insert(int value) {        heap.add(value);        heapifyUp(heap.size() - 1);    }    // 自底向上调整（插入后）    private void heapifyUp(int index) {        if (index > 0 && heap.get(index) > heap.get(parent(index))) {            swap(index, parent(index));            heapifyUp(parent(index));        }    }    // 删除并返回最大值（根节点）    public int extractMax() {        if (heap.isEmpty()) {            throw new IllegalStateException("堆为空！");        }        int max = heap.get(0);        heap.set(0, heap.get(heap.size() - 1));        heap.remove(heap.size() - 1);        heapifyDown(0);        return max;    }    // 自顶向下调整（删除后）    private void heapifyDown(int index) {        int largest = index;        int left = leftChild(index);        int right = rightChild(index);        if (left < heap.size() && heap.get(left) > heap.get(largest)) {            largest = left;        }        if (right < heap.size() && heap.get(right) > heap.get(largest)) {            largest = right;        }        if (largest != index) {            swap(index, largest);            heapifyDown(largest);        }    }    // 交换两个元素    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 boolean isEmpty() {        return heap.isEmpty();    }}

使用示例

下面是一个简单的测试程序，演示如何使用我们刚刚实现的 MaxHeap 类：

public class Main {    public static void main(String[] args) {        MaxHeap maxHeap = new MaxHeap();                maxHeap.insert(10);        maxHeap.insert(20);        maxHeap.insert(15);        maxHeap.insert(30);        maxHeap.insert(40);                System.out.println("堆内容：");        maxHeap.printHeap(); // 输出顺序不一定有序，但满足堆性质                System.out.println("依次取出最大值：");        while (!maxHeap.isEmpty()) {            System.out.print(maxHeap.extractMax() + " ");        }        // 输出：40 30 20 15 10    }}

时间复杂度分析

• 插入（insert）：O(log n)
• 删除最大值（extractMax）：O(log n)
• 获取最大值：O(1)（直接访问根节点）

实际应用场景

最大堆广泛应用于：

• 任务调度系统（优先级高的任务先执行）
• Top-K 问题（如找出最大的 K 个数）
• 图算法（如 Dijkstra 最短路径算法中的优先队列）
• 流数据中动态维护最大值

总结

通过本教程，你已经掌握了 Java最大堆 的基本概念、实现方法和使用场景。堆作为一种高效的堆数据结构，是理解更高级算法（如堆排序、优先队列）的基础。建议你动手编写代码并调试，加深对 最大堆实现 和 优先队列Java 应用的理解。

如果你觉得有帮助，不妨尝试扩展这个类，比如支持泛型、自定义比较器，或者将其封装为 Java 标准库中的 PriorityQueue 的替代实现！