Java 中的优先队列（Priority Queues）

简介

在计算机科学中，优先队列是一种特殊的数据结构，它与普通队列的不同之处在于，队列中的元素按照某种优先级顺序进行处理。在 Java 中，PriorityQueue 类提供了优先队列的实现。它在很多场景下都非常有用，例如任务调度、图算法（如 Dijkstra 算法）等。本文将深入探讨 Java 中优先队列的基础概念、使用方法、常见实践以及最佳实践。

基础概念

优先队列是一种特殊的队列，它的每个元素都有一个优先级。在优先队列中，优先级高的元素会先于优先级低的元素出队。与普通队列遵循的“先进先出（FIFO）”原则不同，优先队列根据元素的优先级来决定出队顺序。

在 Java 中，PriorityQueue 类实现了 Queue 接口，它是基于堆数据结构实现的。堆是一种完全二叉树，其中每个节点的值都大于或等于其子节点的值（最大堆），或者每个节点的值都小于或等于其子节点的值（最小堆）。PriorityQueue 默认实现的是最小堆，即队首元素是队列中最小的元素。

使用方法

创建优先队列

要创建一个优先队列，可以使用以下几种方式：

import java.util.PriorityQueue;

public class PriorityQueueExample {
    public static void main(String[] args) {
        // 创建一个默认的优先队列，基于自然排序
        PriorityQueue<Integer> pq1 = new PriorityQueue<>();

        // 创建一个指定初始容量的优先队列
        PriorityQueue<Integer> pq2 = new PriorityQueue<>(10);

        // 创建一个使用自定义比较器的优先队列
        PriorityQueue<Integer> pq3 = new PriorityQueue<>((a, b) -> b - a); // 最大堆
    }
}

添加元素

可以使用 offer 方法或 add 方法向优先队列中添加元素。这两个方法的功能基本相同，offer 方法在添加失败时会返回 false，而 add 方法在添加失败时会抛出异常。

import java.util.PriorityQueue;

public class PriorityQueueAddExample {
    public static void main(String[] args) {
        PriorityQueue<Integer> pq = new PriorityQueue<>();
        pq.offer(3);
        pq.add(1);
        pq.offer(2);
    }
}

移除元素

使用 poll 方法可以移除并返回优先队列的队首元素。如果队列为空，poll 方法会返回 null。另外，remove 方法也可以移除指定元素，但它的性能相对较差，因为需要遍历队列。

import java.util.PriorityQueue;

public class PriorityQueueRemoveExample {
    public static void main(String[] args) {
        PriorityQueue<Integer> pq = new PriorityQueue<>();
        pq.offer(3);
        pq.offer(1);
        pq.offer(2);

        Integer removed = pq.poll(); // 移除并返回 1
        boolean removedSpecific = pq.remove(2); // 移除元素 2
    }
}

获取队首元素

使用 peek 方法可以获取优先队列的队首元素，但不会移除它。如果队列为空，peek 方法会返回 null。

import java.util.PriorityQueue;

public class PriorityQueuePeekExample {
    public static void main(String[] args) {
        PriorityQueue<Integer> pq = new PriorityQueue<>();
        pq.offer(3);
        pq.offer(1);
        pq.offer(2);

        Integer head = pq.peek(); // 返回 1
    }
}

常见实践

自然排序

当优先队列中的元素类型实现了 Comparable 接口时，优先队列会根据元素的自然顺序进行排序。例如，Integer、String 等类都已经实现了 Comparable 接口。

import java.util.PriorityQueue;

public class NaturalOrderingExample {
    public static void main(String[] args) {
        PriorityQueue<String> pq = new PriorityQueue<>();
        pq.offer("banana");
        pq.offer("apple");
        pq.offer("cherry");

        while (!pq.isEmpty()) {
            System.out.println(pq.poll());
        }
    }
}

输出结果：

apple
banana
cherry

自定义排序

如果需要按照自定义的规则对元素进行排序，可以使用比较器（Comparator）。

import java.util.Comparator;
import java.util.PriorityQueue;

class Person {
    private String name;
    private int age;

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

    public String getName() {
        return name;
    }

    public int getAge() {
        return age;
    }
}

class AgeComparator implements Comparator<Person> {
    @Override
    public int compare(Person p1, Person p2) {
        return p1.getAge() - p2.getAge();
    }
}

public class CustomOrderingExample {
    public static void main(String[] args) {
        PriorityQueue<Person> pq = new PriorityQueue<>(new AgeComparator());
        pq.offer(new Person("Alice", 25));
        pq.offer(new Person("Bob", 20));
        pq.offer(new Person("Charlie", 30));

        while (!pq.isEmpty()) {
            Person person = pq.poll();
            System.out.println(person.getName() + " : " + person.getAge());
        }
    }
}