Java 优先级队列

刺骨的言语ヽ痛彻心扉 2023-10-09 13:55 49阅读 0赞

#### 文章目录 ####

*  Java 优先级队列
 *   *  PriorityQueue简介
     *  继承关系
     *  PriorityQueue示例
     *  Comparable比较器
     *   *  Comparable接口
     *  Comparator比较器
     *   *  Comparator接口
     *  底层原理

## Java 优先级队列 ##

### PriorityQueue简介 ###

`PriorityQueue`，即优先级队列。优先级队列可以保证每次取出来的元素都是队列中的**最小**或**最大**的元素（Java优先级队列默认每次取出来的为最小元素）。

大小关系： 元素的比较可以通过元素本身进行自然排序，也可以通过构造方法传入比较器进行比较。

### 继承关系 ###

![在这里插入图片描述][94b0d7d9a24147099d85b0ea6e0da63b.png]  
通过继承关系图可以知道`PriorityQueue`是`Queen`接口的一个实现类，而`Queen`接口是`Collection`接口的一个实现类，因此其拥有`Collection`接口的基本操作，此外，队列还提供了其他的**插入**，**移除**和**查询**的操作。每个方法存在两种形式：一种是抛出异常（操作失败时），另外一种是返回一个特殊值（null或者false，取决于操作）。  
![在这里插入图片描述][f6bbeeb350f54d03a64becffb4157ae2.png]  
`PriorityQueue`的**peek**和**element**操作的时间复杂度都为**常数**，**add**、**offer**、**remove**以及**poll**的时间复杂度是**log(n)**。

### PriorityQueue示例 ###

import java.util.PriorityQueue;
    
    public class PriorityQueueTest01 {
        
        public static void main(String[] args) {
        
            PriorityQueue<Integer> queue = new PriorityQueue<>();
            queue.add(11);
            queue.add(33);
            queue.add(22);
            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());
        }
    }

**运行结果：**  
![在这里插入图片描述][572133198c9944d5b5c5f299269fbfca.png]  
代码中我们依次添加**11**，**33**，**22**，**55**，**44**五个数据，然后进行删除，通过结果我们发现，每次删除的都为队列中最小元素，即体现了**优先级队列**。

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

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

### Comparable比较器 ###

#### Comparable接口 ####

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

该接口只存在一个`public int compareTo(T o);`方法，该方法表示所在的对象和o对象进行比较，返回值分三种：  
**1：** 表示当前对象大于o对象  
**0：** 表示当前对象等于o对象  
**-1：** 表示当前对象小于o对象

在优先级队列中或者具有比较特征的集合中存储的对象需要实现`Comparable接口`。

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

**代码示例：**  
**Student类：** 当前类实现了`Comparable接口`，即当前类提供了默认的比较方法。

public class Student implements Comparable{
        
        private int id;
        private String name;
        private int age;
        
        public Student(int id, String name, int age) {
        
            this.id = id;
            this.name = name;
            this.age = age;
        }
    
        public int getId() {
        
            return id;
        }
    
        @Override
        public String toString() {
        
            return "Student{" +
                    "id=" + id +
                    ", name='" + name + '\'' +
                    ", age=" + age +
                    '}';
        }
    
        @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,"王昭君",18));
            queue.add(new Student(1,"吕布",19));
            queue.add(new Student(5,"貂蝉",17));
            queue.add(new Student(3,"赵云",20));
            queue.add(new Student(4,"荆轲",18));
    
            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());
        }
    }

**运行结果：**  
![在这里插入图片描述][97b9731568f74e959d7f4dcc054bfa25.png]

### 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对象

**修改PriorityQueueTest类：**

import java.util.PriorityQueue;
    
    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,"王昭君",18));
            queue.add(new Student(1,"吕布",19));
            queue.add(new Student(5,"貂蝉",17));
            queue.add(new Student(3,"赵云",20));
            queue.add(new Student(4,"荆轲",18));
    
            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());
        }
    }

**运行结果：**  
![在这里插入图片描述][6fb880169c774e5699bddc05f62cfab5.png]

### 底层原理 ###

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

transient Object[] queue;

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

**小根堆**（任意一个非叶子节点的权值，都不大于其左右子节点的权值）  
**大根堆**（任意一个非叶子节点的权值，都大于其左右子节点的权值）

可以通过数组来实现优先级队列底层实现，图示：  
![在这里插入图片描述][fb9b96dc36a04092a0748eaf5fcba5a6.png]

对于堆的实现是基于数组来实现的，实际开辟存储空间是数组，对数据的访问按照二叉树来进行访问遍历。**父节点**和**子节点**编号存在联系，父节点和子节点存在如下关系：  
**leftNo = parentNo \* 2 + 1;  
rightNo= parantNo \* 2 + 2;  
parentNo = (nodeNo - 1) / 2;**  
通过以上的三个公式，可以轻易的计算出某个节点的父节点以及子节点的下标，这就是为什么可以使用数组来存储堆的原因。

**以小根堆为例，数据如何进行调整：**

插入数据  
**图示：**  
![在这里插入图片描述][84a5349fec9e40a694f4feb182534a7f.png]  
插入数据首先在有效数据的最后一个位置，即插入在某个叶子节点上，以该节点为待调整节点，和其父节点比较，如果当前节点大于父节点，符合小根堆，不用进行调整，否则需要进行调整，调整至0号根节点或者是其中某一个位置时当前节点大于父节点才终止。

**源码如下：**

//从下往上调整过程  k表示待插入元素位置  x表示待插入数据
    private void siftUpUsingComparator(int k, E x) {
        
            while (k > 0) {
        
                //通过当前待调整节点k找到父节点
                int parent = (k - 1) >>> 1;
                Object e = queue[parent];
                //如果此时父节点数据小于待插入节点数据，满足小根堆，break退出
                if (comparator.compare(x, (E) e) >= 0)
                    break;
                //不满足小根堆，将父节点值插入待插入节点中
                queue[k] = e;
                //待比较位置就指向了父节点
                k = parent;
            }
            queue[k] = x;
        }

删除数据  
**图示：**  
![在这里插入图片描述][34b9ecb9033541488137a4bad4da2201.png]  
因为是小根堆，其堆顶元素最小，所以删除的为堆顶的元素。删除堆顶元素过程，首先记录0号下标的位置，并用最后一个元素替换0号下标的元素，当前的小根堆可能被破坏，需要对堆进行调整，从k指定的位置开始，将逐层向下与当前的左右孩子中较小的进行交换，直到x小于或者等于左右孩子中的任何一个为止。

**源码如下：**

//删除节点 从上往下进行调整  待比较的位置，待调整的元素x
    private void siftDownUsingComparator(int k, E x) {
        
            //将size/2 ,从上往下调整只需要比较到size/2即可，
            //因为size/2时已经到了叶子节点，无需再调整。
            int half = size >>> 1;
            while (k < half) {
        
                //找到当前节点的左孩子
                int child = (k << 1) + 1;
                Object c = queue[child];
                int right = child + 1;//右孩子节点下标
                //找到左右孩子最小的节点，将位置记录到child，值记录在c上
                if (right < size && comparator.compare((E) c, (E) queue[right]) > 0)
                    c = queue[child = right];
                //当左右孩子最小的都大于父节点x值，满足小根堆，结束调整过程
                if (comparator.compare(x, (E) c) <= 0)
                    break;
                //最小的孩子节点小于父节点，不满足小根堆，需要进行调整
                queue[k] = c;
                k = child;
            }
            queue[k] = x;
        }

[94b0d7d9a24147099d85b0ea6e0da63b.png]: https://img-blog.csdnimg.cn/94b0d7d9a24147099d85b0ea6e0da63b.png
[f6bbeeb350f54d03a64becffb4157ae2.png]: https://img-blog.csdnimg.cn/f6bbeeb350f54d03a64becffb4157ae2.png
[572133198c9944d5b5c5f299269fbfca.png]: https://img-blog.csdnimg.cn/572133198c9944d5b5c5f299269fbfca.png
[97b9731568f74e959d7f4dcc054bfa25.png]: https://img-blog.csdnimg.cn/97b9731568f74e959d7f4dcc054bfa25.png
[6fb880169c774e5699bddc05f62cfab5.png]: https://img-blog.csdnimg.cn/6fb880169c774e5699bddc05f62cfab5.png
[fb9b96dc36a04092a0748eaf5fcba5a6.png]: https://img-blog.csdnimg.cn/fb9b96dc36a04092a0748eaf5fcba5a6.png
[84a5349fec9e40a694f4feb182534a7f.png]: https://img-blog.csdnimg.cn/84a5349fec9e40a694f4feb182534a7f.png
[34b9ecb9033541488137a4bad4da2201.png]: https://img-blog.csdnimg.cn/34b9ecb9033541488137a4bad4da2201.png