优享资讯 | 【保姆级】一篇文章带你认识PriorityQueue（优先队列）

掘金后端 ( ) • 2024-07-02 23:47

不少刷过题的小伙伴多少应该听过PriorityQueue（优先队列）这个数据结构，而Java中的PriorityQueue（优先队列）本质其实就是个堆，它的每个元素都根据比较器进行比较后赋予了一个优先级，优先级最高（默认是数值最小的，及俗称的“小根堆”）的元素位于队列的头部（出队列的话优先级高的会先出）。

案例演示

我们举个例子吧

我们需要一个主函数，代码如下：

public static void main(String[] args) {
    PriorityQueue<Employee> queue = new PriorityQueue<Employee>();

    queue.add(new Employee("Lisi", 18));
    queue.add(new Employee("Zhangsan", 99));
    queue.add(new Employee("Wangwu", 22));

    while (!queue.isEmpty()) {
        Employee poll = queue.poll();
        System.out.println("name: " + poll.getName() + " age: " + poll.getAge());
    }
}

自定义一个Employee类，代码如下：

class Employee implements Comparable<Employee> {
    private String name;
    private int age;

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

    public String getName() {
        return name;
    }

    public int getAge() {
        return age;
    }

    @Override
    public int compareTo(Employee o) {
        return this.getAge() - o.getAge();
    }
}

上述例子的输出结果如下：

在这个示例中，我们首先创建了一个PriorityQueue，并添加了一些Employee对象，然后通过循环不断将队列内的元素弹出，并输出弹出元素的name和age，由于在自定义类Employee中，我们使用年龄作为排序的依据（即重写了compareTo()方法）

由于比较的是int类型的数，所以我们可以查看他相关的实现类

从如下源码中不难看出，真正决定元素顺序的逻辑是(x < y) ? -1 : ((x == y) ? 0 : 1)

即如同函数上面介绍里说的

the value 0 if this Integer is equal to the argument Integer; a value less than 0 if this Integer is numerically less than the argument Integer; and a value greater than 0 if this Integer is numerically greater than the argument Integer (signed comparison).

简单翻译下就是：