Java Priority Queue 示例：深入解析与实践

简介

在 Java 编程中，PriorityQueue 是一个非常实用的数据结构，它基于堆（heap）数据结构实现。PriorityQueue 中的元素按照自然顺序（natural ordering）或者根据创建队列时提供的 Comparator 进行排序。这使得它在许多场景下，如任务调度、数据排序等方面发挥着重要作用。本文将通过丰富的示例，详细介绍 PriorityQueue 的基础概念、使用方法、常见实践以及最佳实践。

基础概念

PriorityQueue 是 Java 集合框架中的一部分，它继承自 AbstractQueue 类并实现了 Queue 接口。它的核心特点是元素的出队顺序按照优先级进行，优先级高的元素先出队。这里的优先级可以是元素的自然顺序（例如数字从小到大、字符串按字典序），也可以是通过 Comparator 自定义的顺序。

堆是实现 PriorityQueue 的底层数据结构。堆是一种完全二叉树，它的每个节点的值都大于或等于其子节点的值（最大堆）或小于或等于其子节点的值（最小堆）。PriorityQueue 默认实现的是最小堆，即头部元素是队列中最小的元素。

使用方法

创建 PriorityQueue

创建 PriorityQueue 有多种方式：

import java.util.PriorityQueue;

// 创建一个默认容量为 11 的 PriorityQueue
PriorityQueue<Integer> priorityQueue1 = new PriorityQueue<>(); 

// 创建一个指定初始容量的 PriorityQueue
PriorityQueue<Integer> priorityQueue2 = new PriorityQueue<>(20); 

// 创建一个带有 Comparator 的 PriorityQueue，实现降序排列
PriorityQueue<Integer> priorityQueue3 = new PriorityQueue<>((a, b) -> b - a);

添加元素

可以使用 add 或 offer 方法向 PriorityQueue 中添加元素：

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

删除元素

使用 remove 或 poll 方法删除元素。poll 方法会返回并删除队列头部元素，remove 方法可以删除指定元素：

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

// 删除并返回头部元素
Integer head = queue.poll(); 

// 删除指定元素
queue.remove(2);

获取队列头部元素

使用 peek 方法获取队列头部元素，但不删除它：

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

Integer head = queue.peek();

常见实践

自然排序的 PriorityQueue

以下示例展示了如何使用自然排序的 PriorityQueue：

import java.util.PriorityQueue;

public class NaturalOrderPriorityQueue {
    public static void main(String[] args) {
        PriorityQueue<Integer> queue = new PriorityQueue<>();
        queue.add(5);
        queue.add(1);
        queue.add(3);

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

输出结果：

1
3
5

自定义排序的 PriorityQueue

如果需要自定义排序规则，可以通过实现 Comparator 接口来创建 PriorityQueue：

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

class StringLengthComparator implements Comparator<String> {
    @Override
    public int compare(String s1, String s2) {
        return s1.length() - s2.length();
    }
}

public class CustomOrderPriorityQueue {
    public static void main(String[] args) {
        PriorityQueue<String> queue = new PriorityQueue<>(new StringLengthComparator());
        queue.add("apple");
        queue.add("banana");
        queue.add("a");

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