Java最小堆详解（从零开始掌握PriorityQueue与堆数据结构）

在Java中，我们通常使用内置的 PriorityQueue 类来实现最小堆。默认情况下，PriorityQueue 就是一个最小堆，非常适合用来处理需要频繁获取最小值的场景。

为什么使用最小堆？

最小堆的优势在于：

• 插入（Insert）操作时间复杂度为 O(log n)
• 获取最小值（Peek）操作时间复杂度为 O(1)
• 删除最小值（Poll）操作时间复杂度为 O(log n)

这些高效的性能使得堆数据结构成为解决Top-K、合并K个有序链表等问题的首选工具。

使用PriorityQueue实现最小堆

Java标准库中的 java.util.PriorityQueue 默认就是最小堆。下面是一个简单的示例：

import java.util.PriorityQueue;public class MinHeapExample {    public static void main(String[] args) {        // 创建一个最小堆（默认行为）        PriorityQueue<Integer> minHeap = new PriorityQueue<>();        // 添加元素        minHeap.offer(10);        minHeap.offer(5);        minHeap.offer(20);        minHeap.offer(1);        // 获取并移除堆顶（最小值）        while (!minHeap.isEmpty()) {            System.out.println(minHeap.poll()); // 输出：1, 5, 10, 20        }    }}  

运行上述代码，你会看到输出结果是按从小到大的顺序排列的，这正是最小堆的特性体现。

自定义对象的最小堆

如果要存储自定义对象（比如学生、任务等），你需要提供比较规则。可以通过实现 Comparable 接口或传入 Comparator 来实现。

import java.util.PriorityQueue;import java.util.Comparator;class Task {    String name;    int priority;    Task(String name, int priority) {        this.name = name;        this.priority = priority;    }    @Override    public String toString() {        return name + "(优先级:" + priority + ")";    }}public class CustomMinHeap {    public static void main(String[] args) {        // 按优先级升序（数值越小优先级越高）        PriorityQueue<Task> taskQueue = new PriorityQueue<>(            Comparator.comparingInt(t -> t.priority)        );        taskQueue.offer(new Task("写报告", 3));        taskQueue.offer(new Task("回邮件", 1));        taskQueue.offer(new Task("开会", 2));        while (!taskQueue.isEmpty()) {            System.out.println(taskQueue.poll());        }        // 输出：        // 回邮件(优先级:1)        // 开会(优先级:2)        // 写报告(优先级:3)    }}  

手动实现最小堆（可选进阶）

虽然 PriorityQueue 已经足够强大，但理解底层原理有助于你更深入掌握堆数据结构。下面是一个简化版的最小堆实现：

import java.util.ArrayList;import java.util.List;public class SimpleMinHeap {    private List<Integer> heap = new ArrayList<>();    // 插入元素    public void insert(int value) {        heap.add(value);        heapifyUp(heap.size() - 1);    }    // 获取最小值    public int peek() {        if (heap.isEmpty()) throw new RuntimeException("堆为空");        return heap.get(0);    }    // 移除最小值    public int poll() {        if (heap.isEmpty()) throw new RuntimeException("堆为空");        int min = heap.get(0);        int last = heap.remove(heap.size() - 1);        if (!heap.isEmpty()) {            heap.set(0, last);            heapifyDown(0);        }        return min;    }    private void heapifyUp(int index) {        while (index > 0) {            int parent = (index - 1) / 2;            if (heap.get(index) >= heap.get(parent)) break;            swap(index, parent);            index = parent;        }    }    private void heapifyDown(int index) {        int left, right, smallest;        while (true) {            left = 2 * index + 1;            right = 2 * index + 2;            smallest = index;            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 == index) break;            swap(index, smallest);            index = smallest;        }    }    private void swap(int i, int j) {        int temp = heap.get(i);        heap.set(i, heap.get(j));        heap.set(j, temp);    }    public boolean isEmpty() {        return heap.isEmpty();    }}  

总结

通过本教程，你已经掌握了：

• 什么是Java最小堆及其核心性质
• 如何使用 PriorityQueue 快速实现最小堆
• 如何处理自定义对象的排序逻辑
• （可选）手动实现最小堆的基本原理

无论你是准备面试，还是开发实际项目，理解PriorityQueue教程中的这些知识点都将大有裨益。赶快动手试试吧！

关键词回顾：Java最小堆、最小堆实现、PriorityQueue教程、堆数据结构