Java中的PriorityQueue类过程详解

Java中的PriorityQueue类是一个基于优先级堆的无界优先级队列，它以小顶堆的形式来维护队列。在Java Collections Framework中，它实现了Queue接口，因此可以使用Queue的所有方法。

PriorityQueue类的基本性质

1. 元素按照优先级排序：PriorityQueue类的元素默认是按照自然顺序排序的，也可以通过指定Comparator来实现自定义排序；
2. 小顶堆：元素在队列中的位置满足小顶堆的性质，即任意节点的值都小于它的子节点的值；
3. 无界队列：使用时，如果不指定初始容量，PriorityQueue类默认使用一个初始容量为11的队列。当队列元素超过容量时，自动扩容。

PriorityQueue类的常用方法

add(E e) / offer(E e)

向队列中添加元素。

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

peek()

获取队列中的头元素，但不从队列中删除。

PriorityQueue<Integer> pq = new PriorityQueue<>(Arrays.asList(2, 3, 1));
System.out.println(pq.peek()); // 1

poll()

获取队列中的头元素，并将其从队列中删除。

PriorityQueue<Integer> pq = new PriorityQueue<>(Arrays.asList(2, 3, 1));
System.out.println(pq.poll()); // 1
System.out.println(pq); // [2, 3]

remove(Object o)

从队列中删除指定元素。

PriorityQueue<Integer> pq = new PriorityQueue<>(Arrays.asList(2, 3, 1));
pq.remove(2);
System.out.println(pq); // [1, 3]

removeAll(Collection<?> c)

从队列中删除指定集合中的所有元素。

PriorityQueue<Integer> pq = new PriorityQueue<>(Arrays.asList(2, 3, 1));
pq.removeAll(Arrays.asList(2, 3));
System.out.println(pq); // [1]

示例说明

示例1

假设我们有一个Person类，其中有两个属性：姓名和年龄。需要将多个Person对象按照年龄从小到大的顺序排列，则可以使用PriorityQueue类进行处理。

public 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;
    }
}

PriorityQueue<Person> pq = new PriorityQueue<>(Comparator.comparingInt(Person::getAge));
pq.add(new Person("Alice", 25));
pq.add(new Person("Bob", 23));
pq.add(new Person("Charlie", 28));
System.out.println(pq.poll().getName()); // Bob
System.out.println(pq.poll().getName()); // Alice
System.out.println(pq.poll().getName()); // Charlie

示例2

假设我们需要对一个数组进行升序排列，则可以使用PriorityQueue类进行处理。

int[] nums = {3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5};
PriorityQueue<Integer> pq = new PriorityQueue<>();
for (int num : nums) {
    pq.add(num);
}
System.out.println(pq); // [1, 1, 2, 3, 3, 4, 5, 5, 5, 6, 9]

总结

PriorityQueue类是一个很常用的数据结构，它可以帮助我们快速、方便地实现元素按照优先级排序的功能。在使用时，要注意元素在队列中的位置满足小顶堆的性质。