Java 中实现优先队列

简介

优先队列是一种特殊的队列，它与普通队列不同，普通队列遵循先进先出（FIFO）原则，而优先队列中的元素会根据其优先级进行排序，优先级高的元素会先出队。在 Java 中，PriorityQueue 类是实现优先队列的常用方式，它基于堆数据结构实现。本文将详细介绍 Java 中优先队列的基础概念、使用方法、常见实践以及最佳实践，帮助读者深入理解并高效使用 Java 优先队列。

基础概念

优先队列定义

优先队列是一种抽象数据类型，它支持插入元素和删除最小（或最大）元素这两个主要操作。插入元素时，元素会被添加到队列中合适的位置，以保证队列的顺序；删除操作会移除优先级最高的元素。

堆数据结构

Java 中的 PriorityQueue 基于堆（通常是最小堆）实现。堆是一种完全二叉树，每个节点的值都小于或等于其子节点的值（最小堆）。堆的特性使得插入和删除操作的时间复杂度都为 $O(log n)$，其中 $n$ 是堆中元素的数量。

Java 中的 PriorityQueue 类

PriorityQueue 是 Java 集合框架中的一个类，位于 java.util 包中。它实现了 Queue 接口，因此可以像普通队列一样使用，同时又具备优先队列的特性。PriorityQueue 可以存储任意类型的元素，但元素必须是可比较的，或者在创建 PriorityQueue 时提供一个比较器（Comparator）。

使用方法

创建 PriorityQueue

以下是创建 PriorityQueue 的几种常见方式：

import java.util.PriorityQueue;

public class PriorityQueueExample {
    public static void main(String[] args) {
        // 创建一个存储整数的优先队列，默认是最小堆
        PriorityQueue<Integer> minHeap = new PriorityQueue<>();

        // 创建一个存储整数的优先队列，使用自定义比较器实现最大堆
        PriorityQueue<Integer> maxHeap = new PriorityQueue<>((a, b) -> b - a);

        // 创建一个存储自定义对象的优先队列，需要提供比较器
        PriorityQueue<Person> personQueue = new PriorityQueue<>((p1, p2) -> p1.getAge() - p2.getAge());
    }
}

class Person {
    private String name;
    private int age;

    public Person(String name, int age) {
        this.name = name;
        this.age = age;
    }

    public int getAge() {
        return age;
    }
}

插入元素

使用 add() 或 offer() 方法向优先队列中插入元素：

PriorityQueue<Integer> queue = new PriorityQueue<>();
queue.add(3);
queue.offer(1);
queue.add(2);

删除元素

使用 poll() 方法删除并返回队列中优先级最高的元素：

int min = queue.poll(); // 返回最小元素 1

获取队首元素

使用 peek() 方法获取队首元素，但不删除它：

int peeked = queue.peek(); // 获取队首元素，但不删除

常见实践

排序问题

优先队列可以用于排序。例如，对一个数组进行排序：

import java.util.PriorityQueue;

public class SortingWithPriorityQueue {
    public static void main(String[] args) {
        int[] arr = {3, 1, 2};
        PriorityQueue<Integer> queue = new PriorityQueue<>();
        for (int num : arr) {
            queue.add(num);
        }
        while (!queue.isEmpty()) {
            System.out.print(queue.poll() + " "); // 输出 1 2 3
        }
    }
}

合并多个有序列表

假设有多个有序列表，需要将它们合并成一个有序列表：

import java.util.ArrayList;
import java.util.List;
import java.util.PriorityQueue;

class ListNode {
    int val;
    ListNode next;
    ListNode(int val) {
        this.val = val;
    }
}

public class MergeKSortedLists {
    public ListNode mergeKLists(List<ListNode> lists) {
        PriorityQueue<ListNode> queue = new PriorityQueue<>((a, b) -> a.val - b.val);
        for (ListNode node : lists) {
            if (node != null) {
                queue.add(node);
            }
        }
        ListNode dummy = new ListNode(0);
        ListNode tail = dummy;
        while (!queue.isEmpty()) {
            ListNode minNode = queue.poll();
            tail.next = minNode;
            tail = tail.next;
            if (minNode.next != null) {
                queue.add(minNode.next);
            }
        }
        return dummy.next;
    }
}

最佳实践

选择合适的比较器

在使用优先队列存储自定义对象时，需要提供合适的比较器。比较器的实现要保证其满足传递性、自反性和对称性，否则可能会导致队列行为异常。

注意空指针异常

在使用 poll() 和 peek() 方法时，要确保队列不为空，否则会抛出 NoSuchElementException 异常。可以使用 isEmpty() 方法进行检查。

性能考虑

优先队列的插入和删除操作的时间复杂度为 $O(log n)$，因此在处理大量数据时，性能表现较好。但如果需要频繁访问队列中的元素，优先队列可能不是最佳选择。

小结

本文介绍了 Java 中优先队列的基础概念、使用方法、常见实践以及最佳实践。优先队列是一种非常有用的数据结构，它在排序、合并有序列表等场景中有着广泛的应用。通过合理使用 PriorityQueue 类和比较器，可以高效地解决各种问题。在使用过程中，要注意比较器的实现、空指针异常和性能问题。

参考资料

《算法导论》