通过继承关系图可以知道 PriorityQueue 是 Queue 接口的一个实现类，而 Queue 接口是 Collection 接口的一个实现类，因此其拥有 Collection 接口的基本操作，此外，队列还提供了其他的插入，移除和查询的操作。每个方法存在两种形式：一种是抛出异常（操作失败时），另一种是返回一个特殊值（null 或 false）。

PriorityQueue 的 peek 和 element 操作的时间复杂度都为常数，add，offer，remove 以及 poll 的时间复杂度是 log（n）。

PriorityQueue 示例


impot java.util.PriorityQueue;
 
public class PriorityQueueTest{
    public static void main(String[] args){
        PriorityQueue<Integer> queue = new PriorityQueue<>();
        queue.add(11);
        queue.add(22);
        queue.add(33);
        queue.add(55);
        queue.add(44);
        System.out.println(queue.remove());
        System.out.println(queue.remove());
        System.out.println(queue.remove());
        System.out.println(queue.remove());
        System.out.println(queue.remove());
    }
}

运行结果：

代码中我们依次添加11，22，33，55，44五个数据，然后进行删除，通过结果我们发现，每次删除的都为队列中最小元素，即体现了优先级队列。

结论：优先级队列默认每次获取队列最小的元素，也可以通过 comparator 比较器来自定义每次获取为最小还是最大。

注意:优先级队列中不可以存储 null。

二. Comparable 比较器

Compare 接口


public interface Comparable<T>{
    public int compareTo(T o);
}

该接口只存在一个 public int compareTo(T o); 方法，该方法表示所在的对象和 o 对象进行比较，返回值分三种：

1：表示该对象大于 o 对象

0：表示该对象等于 o 对象

-1：表示该对象小于 o 对象

需求：在优先级队列中存储对象学生，每个学生有 id，name 两个属性，并且使优先级队列每次按照学生的 id 从小到大取出。

代码示例：

Student 类：当前类实现了 Comparable 接口，即当前类提供了默认的比较方法。


    public class Student implements Comparable{
        private int id;
        private String name;
        
        public Student(int id,String name,int age){
            this.id = id;
            this.name = name;
        }
        
        public int getId(){
            return id;
        }
        
        @Override
        public String toString(){
            return "Student{" +
                    "id=" + id +
                    ", name='" + name + '\'' +
                    '}';
        }
        
        @Override
        public int compareTo(Object o){
            Student o1 = (Student)o;
            return this.id - o1.id;
        }
    }

PriorityQueueTest 类：


public class PriorityQueueTest {
    public static void main(String[] args) {
        PriorityQueue<Student> queue = new PriorityQueue<>();
        queue.add(new Student(2,"Jack"));
        queue.add(new Student(1,"Mary"));
        queue.add(new Student(5,"Mcan"));
        queue.add(new Student(4,"Scolt"));
        queue.add(new Student(3,"Tina"));
        System.out.println(queue.remove());
        System.out.println(queue.remove());
        System.out.println(queue.remove());
        System.out.println(queue.remove());
        System.out.println(queue.remove());
    }
}

运行结果：

三. Comparator 比较器

新需求：如果使优先级队列按照学生 id 从大到小取出呢？我们很快就会想到修改 Student 类的compareTo 方法，使 return o1.id - this.id；这样当然可以实现我们的新需求。但是有很多时候类的compareTo 方法是不能修改的，比如 JDK 给我们提供的源代码，在不修改 compareTo 方法的前提下实现需求，只能用 comparator 比较器了。

Comparator 接口


public interface Comparator<T>{
    int compare(T o1,T o2);
}

该接口只存在一个 int compare(T o1,T o2);方法，该方法需要参数是两个待比较的对象，返回结果是 int 类型：

1：表示 o1对象大于 o2 对象

0：表示 o1对象等于 o2 对象

-1：表示 o1对象小于 o2 对象


public class PriorityQueueTest {
    public static void main(String[] args) {
        PriorityQueue<Student> queue = new PriorityQueue<>(new Comparator<Student>() {
 
            @Override
            public int compare(Student o1, Student o2) {
                return o2.getId() - o1.getId();
        }
    })
    queue.add(new Student(2, "Jack"));
    queue.add(new Student(1, "Mary"));
    queue.add(new Student(5, "Mcan"));
    queue.add(new Student(4, "Scolt"));
    queue.add(new Student(3, "Tina"));
    System.out.println(queue.remove());
    System.out.println(queue.remove());
    System.out.println(queue.remove());
    System.out.println(queue.remove());
    System.out.println(queue.remove());
}
}

运行结果：

四. 底层原理

优先级队列是如何保证每次取出的是队列中最小（最大）的元素的呢？查看源代码，底层的存储结构为一个数组

transient Object[] queue;

表面上是一个数组结构，实际上优先队列采用的是堆的形式来进行存储的，通过调整小堆或大堆来保证每次取出的元素为队列中的最小或最大。

详见：https://blog.csdn.net/Lucky_mzc/article/details/123331280?spm=1001.2014.3001.5501

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/寸_铁/article/detail/895196