Java PriorityQueue类

Java `PriorityQueue`类

原文： https://howtodoinjava.com/java/collections/java-priorityqueue/

Java PriorityQueue类是一种队列数据结构实现，其中，根据对象的优先级处理对象。它与遵循 FIFO （先进先出）算法的标准队列不同。

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

Priority Queue

优先队列

1. `PriorityQueue`特性

让我们记下PriorityQueue的几个要点。

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

2. Java `PriorityQueue`示例

让我们看看对象的排序如何影响PriorityQueue中的添加和删除操作。在给定的示例中，对象的类型为Employee。 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 + "]";
    }
}

2.1 自然排序

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]

2.2 使用比较器自定义顺序

让我们使用基于 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]

3. Java `PriorityQueue`构造器

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

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

4. Java `PriorityQueue`方法

您应该知道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()：返回包含此队列中所有元素的数组。

5. 总结

在此 Java 队列教程中，我们学习了使用PriorityQueue类，该类能够按默认的自然顺序或指定比较器的自定义顺序存储元素。

我们还了解了PriorityQueue类的一些重要方法和构造器。

将我的问题放在评论部分。

学习愉快！

参考文献：

PriorityQueue类 Java 文档

Java PriorityQueue类

1. PriorityQueue特性

2. Java PriorityQueue示例