1. PriorityQueue 特性

• PriorityQueue 是一个无界队列并且动态增长。默认初始容量为“11”，可以在适当的构造函数中使用 initialCapacity 参数覆盖它。
• 它不允许 NULL 对象。
• 添加到 PriorityQueue 的对象必须具有可比性。
• 优先级队列的对象默认按自然顺序排列。
• Comparator 可用于队列中对象的自定义排序。
• 优先级队列的头部是基于自然排序或者基于比较器排序的最少元素。当我们轮询队列时，它从队列中返回头对象。
• 如果存在多个具有相同优先级的对象，则它可以随机轮询其中的任何一个。
• PriorityQueue 不是线程安全的。在并发环境中使用 PriorityBlockingQueue。
• 它为添加和轮询方法提供 O(log(n)) 时间。

Java PriorityQueue 的方法

• boolean add(object) ：将指定元素插入此优先级队列。
• boolean offer(object) ：将指定的元素插入此优先级队列。
• boolean remove(object) ：从此队列中移除指定元素的单个实例（如果存在）。
• Object poll() ：检索并移除此队列的头部，如果此队列为空，则返回 null。
• Object element() ：检索但不删除此队列的头部，如果此队列为空，则抛出 NoSuchElementException。
• Object peek() ：检索但不删除此队列的头部，如果此队列为空，则返回 null。
• void clear() ：从此优先级队列中删除所有元素。
• Comparator Comparator() ：返回用于对该队列中的元素进行排序的比较器，如果该队列根据其元素的自然顺序进行排序，则返回 null。
• boolean contains(Object o) ：如果此队列包含指定的元素，则返回 true。
• Iterator iterator() ：返回此队列中元素的迭代器。
• int size() ：返回此队列中的元素数。
• Object[] toArray() ：返回一个包含此队列中所有元素的数组。

Java PriorityQueue 类是一个队列数据结构实现，其中对象根据它们的优先级进行处理。

在优先队列中，添加的对象是根据它们的优先级。
默认情况下，优先级由对象的自然顺序决定。
默认优先级可以被队列构建时提供的 Comparator 覆盖。

Java PriorityQueue 示例

Employee 类实现了 Comparable 接口，默认情况下，该接口使对象可以通过员工“id”字段进行比较。

public class Employee implements Comparable<Employee> {
    private Long id;
    private String name;
    private LocalDate dob;
    public Employee(Long id, String name, LocalDate dob) {
        super();
        this.id = id;
        this.name = name;
        this.dob = dob;
    }

    @Override
    public int compareTo(Employee emp) {
        return this.getId().compareTo(emp.getId());
    }
    //Getters and setters
    @Override
    public String toString() {
        return "Employee [id=" + id + ", name=" + name + ", dob=" + dob + "]";
    }
}

自然排序

Java PriorityQueue 示例，用于添加和轮询基于自然顺序进行比较的元素。

PriorityQueue<Employee> priorityQueue = new PriorityQueue<>();

priorityQueue.add(new Employee(1l, "AAA", LocalDate.now()));
priorityQueue.add(new Employee(4l, "CCC", LocalDate.now()));
priorityQueue.add(new Employee(5l, "BBB", LocalDate.now()));
priorityQueue.add(new Employee(2l, "FFF", LocalDate.now()));
priorityQueue.add(new Employee(3l, "DDD", LocalDate.now()));
priorityQueue.add(new Employee(6l, "EEE", LocalDate.now()));
while(true) 
{
    Employee e = priorityQueue.poll();
    System.out.println(e);

    if(e == null) break;
}

输出:

Employee [id=1, name=AAA, dob=2018-10-31]
Employee [id=2, name=FFF, dob=2018-10-31]
Employee [id=5, name=BBB, dob=2018-10-31]
Employee [id=4, name=CCC, dob=2018-10-31]
Employee [id=3, name=DDD, dob=2018-10-31]
Employee [id=6, name=EEE, dob=2018-10-31]

使用比较器的自定义排序

让我们使用基于 Java 8 lambda 的比较器语法重新定义自定义排序并验证结果。

//Comparator for name field
Comparator<Employee> nameSorter = Comparator.comparing(Employee::getName);
PriorityQueue<Employee> priorityQueue = new PriorityQueue<>( nameSorter );

priorityQueue.add(new Employee(1l, "AAA", LocalDate.now()));
priorityQueue.add(new Employee(4l, "CCC", LocalDate.now()));
priorityQueue.add(new Employee(5l, "BBB", LocalDate.now()));
priorityQueue.add(new Employee(2l, "FFF", LocalDate.now()));
priorityQueue.add(new Employee(3l, "DDD", LocalDate.now()));
priorityQueue.add(new Employee(6l, "EEE", LocalDate.now()));
while(true) 
{
    Employee e = priorityQueue.poll();
    System.out.println(e);

    if(e == null) break;
}

输出:

Employee [id=1, name=AAA, dob=2018-10-31]
Employee [id=5, name=BBB, dob=2018-10-31]
Employee [id=4, name=CCC, dob=2018-10-31]
Employee [id=3, name=DDD, dob=2018-10-31]
Employee [id=6, name=EEE, dob=2018-10-31]
Employee [id=2, name=FFF, dob=2018-10-31]

Java PriorityQueue 的构造函数

PriorityQueue 类提供了 6 种不同的方式来构造 Java 中的优先队列。

• PriorityQueue() ：使用默认初始容量 (11) 构造空队列，该队列根据元素的自然顺序对其进行排序。
• PriorityQueue(Collection c) ：构造包含指定集合中元素的空队列。
• PriorityQueue(int initialCapacity) ：构造具有指定初始容量的空队列，该队列根据元素的自然顺序对其进行排序。
• PriorityQueue(int initialCapacity, Comparator Comparator) ：构造具有指定初始容量的空队列，根据指定的比较器对其元素进行排序。
• PriorityQueue(PriorityQueue c) ：构造包含指定优先级队列中元素的空队列。
• PriorityQueue(SortedSet c) ：构造包含指定排序集中元素的空队列。