什么是优先级队列

队列是一种先进先出(FIFO)的数据结构，优先级队列也是一个队列，但并不是单纯的先进先出，而是把优先级最高的先出去，优先级队列内部结构就是堆（Heap）

常用接口介绍

Java集合框架中提供了PriorityQueue 和 PriorityBlockingQueue两种类型的优先级队列， PriorityQueue是线程不安全的，PriorityBlockingQueue是线程安全的，

PriorityQueue特性

1. 使用时必须导入PriorityQueue所在的包，即：

import java.util.PriorityQueue;

2. PriorityQueue中放置的元素必须要能够比较大小，不能插入无法比较大小的对象，否则会抛出 ClassCastException异常
3. 不能插入null对象，否则会抛出NullPointerException
4. 没有容量限制，可以插入任意多个元素，其内部可以自动扩容
5. 插入和删除元素的时间复杂度为 O ( l o g 2 N ) O(log_2N) O(log2N)
6. PriorityQueue底层使用了堆数据结构

PriorityQueue常用接口介绍

优先级队列构造

插入/删除/获取优先级元素

import java.util.PriorityQueue;

public class Test {
          
   
    public static void main(String[] args) {
          
   
        PriorityQueue<Integer> q = new PriorityQueue<>();
        int [] arr = {
          
   9, 5, 2 ,7, 3, 8, 6};
        // 将数组元素插入到队列中
        for (int x : arr) {
          
   
            q.offer(x);
        }
        // 获取队列 q 中有效元素个数
        System.out.println(q.size());
        // 获取优先级最高元素
        System.out.println(q.peek());
        // 将优先级最高元素弹出，并返回
        while (! q.isEmpty()) {
          
   
            System.out.println(q.poll());
        }

        q.offer(0);
        // 清空
        q.clear();
        if (q.isEmpty()) {
          
   
            System.out.println("优先级队列 null");
        } else {
          
   
            System.out.println("优先级队列 !null");
        }
    }
}

Comparable 接口

Comparable接口是 Java 标准库中内置的一个 “接口” interface，里面只有一个抽象方法，comparaTo(Object other),通过这个方法来指定对象自身和另一个对象之间的大小关系。

java.lang.Comparable;

Comparator接口，也有类似的作用，Comparator接口，哪个类需要比较，就需要让这个类实现该接口。

优先级队列的应用

1. 用来排序（堆排序）
2. 用来排序提取前 k 个元素