Java集合框架（PriorityQueue优先级队列讲解）

矫情吗；* 2024-04-23 15:34 84阅读 0赞

## 前言： ##

> Java集合框架中提供了PriorityQueue和PriorityBlockingQueue两种类型的优先级队列，**PriorityQueue是线程不安全的，PriorityBlockingQueue是线程安全的，本文主要介绍PriorityQueue**  
>

priorityQueue在Java集合框架中的关系如下：  
![6136729e88fe440ba2881e9b068a47ad.png][]

## 一、使用PriorityQueue的注意点 ##

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

> **import java.util.PriorityQueue**

2. **PriorityQueue中放置的元素必须要能够比较大小，不能插入无法比较大小的对象，否则会抛出  
ClassCastException异常**

3. 不能插入null对象，否则会抛出NullPointerException

4. 没有容量限制，可以插入任意多个元素，其内部可以自动扩容

5. 插入和删除元素的**时间复杂度为log以2为底的n**

6. PriorityQueue底层使用了堆数据结构

7. PriorityQueue默认情况下是小堆---即每次获取到的元素都是最小的元素（**想要变成大堆，需要我们重新比较方法、默认的比较方法是Comparable接口中的compareTo方法）**

--------------------

## 二、PriorityQueue常用接口介绍 ##

###    1. 优先级队列的构造 ###

?此处只是列出了**PriorityQueue中常见的几种构造方式**，其他的大家可以参考帮助文档。

<table> 
 <tbody> 
  <tr> 
   <td>构造器</td> 
   <td>功能介绍</td> 
  </tr> 
  <tr> 
   <td>PriorityQueue()</td> 
   <td>创建一个空的优先级队列，<strong>默认容量是11</strong></td> 
  </tr> 
  <tr> 
   <td>PriorityQueue(int<br> initialCapacity)</td> 
   <td>创建一个<strong>初始容量为initialCapacity</strong>的优先级队列，<span style="background-color:#38d8f0;">注意：</span><strong>initialCapacity不能小于1，否则会抛IllegalArgumentException异</strong>常</td> 
  </tr> 
  <tr> 
   <td>PriorityQueue(Collection&lt;?<br> extends E&gt; c)</td> 
   <td>用一个集合来创建优先级队列</td> 
  </tr> 
  <tr> 
   <td><strong><code>PriorityQueue(Comparator&lt;? super E&gt;&nbsp;comparator)</code></strong></td> 
   <td>创建具有<strong>默认初始容量的优先级队列</strong>，并根据<strong>指定的比较器</strong>对其元素进行比较</td> 
  </tr> 
  <tr> 
   <td><strong><code>PriorityQueue(int&nbsp;initialCapacity, Comparator &lt;? super E&gt;&nbsp;comparator)</code></strong></td> 
   <td> <p>创建一个<strong>初始容量为<code><strong>initialCapacity</strong>的优先级队列</code></strong>，根据<strong>指定的比较器</strong>对其元素进行比较</p> <p><span style="background-color:#38d8f0;">注意：</span><strong>initialCapacity不能小于1，否则会抛IllegalArgumentException异</strong>常</p> </td> 
  </tr> 
 </tbody> 
</table>

### 2、PriorityQueue中对元素的比较 ###

看完了构造方法，我们重新来思考一个问题

优先级队列是如何实现有序的呢？因为优先级队列就是借助小根堆来实现的

在实现小根堆的过程我们知道这其中一定发生了元素的比较，所以PriorityQueue中的元素必须要能够比较大小，那么PriorityQueue是如何进行元素的比较呢？

> PriorityQueue采用了：  
> **Comparble和Comparator两种方式。**
> 
>   
> 1. **Comparble是默认的内部比较方式**，如果用户插入自定义类型**对象时，该类对象必须要实现Comparble接口，并覆写compareTo方法**
> 
>   
> 2. 用户也可以选择使用比较器对象，如果用户**插入自定义类型对象时，必须要提供一个比较器类，让该类实现Comparator接口并覆写compare方法。**

![62cf644e28834ca1946d46b85093ca3b.png][]

我们看到这里程序报错了，为什么呢？因为我们插入的Child对象是不可比较的（**即没有实现Comparable接口又没有采用自定义的比较器）**

可以看到

![514b7ee1b7b94b95bc71024d827c16f0.png][]

**即我们采用了默认的比较方法Comparable接口中的compareTo方法**

![12359ab31da6414890718ec8e4635328.png][]

此时我们再次看一下报错信息

![9b358385506c4251973f1556f0e39ba8.png][]**?看来是在往PriorityQueue中插入元素的时候出现了问题**

?那么我们打开PriorityQueue的源码看一下（**下面是PriorityQueue中offer方法的源码）**

![a85492ac28b4486da6b857aaf4ffea11.png][]

再看看shiftUp的源码

![3876af263f874913992e68769f1967f6.png][]

继续点进去siftUpComparable

![4bd2300184834f98ac05c40911221282.png][]

此时再回过头来看看我们放到PriorityQueue中的Child对象，**他即没有自定义比较器又没有实现Comparable接口，**当然报错呀！

那么好吧我们在Child类中实现Comparable接口，按年龄进行比较

>     import java.util.PriorityQueue;
>     class Child implements Comparable<Child>{
>         int age;
>         String name;
>     
>         public Child(int age, String name) {
>             this.age = age;
>             this.name = name;
>         }
>     
>         @Override
>         public int compareTo(Child o) {
>             return this.age - o.age;  // 默认实现小根堆
>         }
>     
>         @Override
>         public String toString() {
>             return "Child{" +
>                     "age=" + age +
>                     ", name='" + name + '\'' +
>                     '}';
>         }
>     }
>     public class TestPriorityQueue {
>         public static void main(String[] args) {
>             PriorityQueue<Child> priorityQueue = new PriorityQueue<>();
>     
>             priorityQueue.offer(new Child(12, "小亮"));
>             priorityQueue.offer(new Child(11, "小红"));
>             priorityQueue.offer(new Child(8, "小强"));
>             System.out.println(priorityQueue);
>         }
>     }
> 
> ![5fcc6327830540928f0e8730e2f90a1d.png][]

如果要实现大根堆，也好办?

![2e75f826db7146559a3f707e14f18c05.png][]

上面我们是实现了Compable接口，那么如果我们自定义一个年龄比较器呢？

>     class Child {
>         int age;
>         String name;
>     
>         public Child(int age, String name) {
>             this.age = age;
>             this.name = name;
>         }
>     
>         @Override
>         public String toString() {
>             return "Child{" +
>                     "age=" + age +
>                     ", name='" + name + '\'' +
>                     '}';
>         }
>     }
>     class AgeComparator implements Comparator<Child> {
>     
>         @Override
>         public int compare(Child o1, Child o2) {
>             return o1.age - o2.age; // 实现小根堆
>             // return o2.ae - o1.age 实现大根堆
>         }
>     }
>     public class TestPriorityQueue {
>         public static void main(String[] args) {
>             AgeComparator ageComparator = new AgeComparator();
>             // 创建具有默认初始容量的 PriorityQueue ，并根据指定的比较器对其元素进行排序。
>             PriorityQueue<Child> priorityQueue = new PriorityQueue<>(ageComparator);
>             // 可以看到这里我的Child对象虽然没有实现Comparable接口，但因为我们对Child对象自定义了一个年龄比较器，所以插入元素不会报错
>             priorityQueue.offer(new Child(12, "小亮"));
>             priorityQueue.offer(new Child(11, "小红"));
>             priorityQueue.offer(new Child(8, "小强"));
>             System.out.println(priorityQueue);
>         }
>     }
> 
> ![6b861a61a54448e7b89ac8ea98a0814f.png][]

--------------------

### 3、插入/删除/获取优先级最高的元素 ###

<table> 
 <tbody> 
  <tr> 
   <td>函数名</td> 
   <td>功能介绍</td> 
  </tr> 
  <tr> 
   <td>boolean<br> offer(E e)</td> 
   <td>插入元素e，插入成功返回true，如果e对象为空，抛出NullPointerException异常，时<br> 间复杂度 ，注意：空间不够时候会进行扩容</td> 
  </tr> 
  <tr> 
   <td>E peek()</td> 
   <td>获取优先级最高的元素，如果优先级队列为空，返回null</td> 
  </tr> 
  <tr> 
   <td>E poll()</td> 
   <td>移除优先级最高的元素并返回，如果优先级队列为空，返回null</td> 
  </tr> 
  <tr> 
   <td>int size()</td> 
   <td>获取有效元素的个数</td> 
  </tr> 
  <tr> 
   <td>void<br> clear()</td> 
   <td>清空</td> 
  </tr> 
  <tr> 
   <td> <p>boolean&nbsp;</p> <p>isEmty()</p> </td> 
   <td> 
    <table> 
     <tbody> 
      <tr> 
       <td>检测优先级队列是否为空，为空返回true</td> 
      </tr> 
     </tbody> 
    </table></td> 
  </tr> 
 </tbody> 
</table>

[6136729e88fe440ba2881e9b068a47ad.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/23/00d4507de02d44a082ba066d1a4d5cc0.png
[62cf644e28834ca1946d46b85093ca3b.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/23/6eb57a841ac84deabeba2cb62567389b.png
[514b7ee1b7b94b95bc71024d827c16f0.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/23/76954acd1a804b07876a6b1d557743d1.png
[12359ab31da6414890718ec8e4635328.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/23/281660f97b1b48a48d5d57ad2e57f614.png
[9b358385506c4251973f1556f0e39ba8.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/23/762843d67cdc4b3ca69852dba4146c4c.png
[a85492ac28b4486da6b857aaf4ffea11.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/23/e2207797d7c34c79816c08225cd0003c.png
[3876af263f874913992e68769f1967f6.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/23/6d29337846174a6abc1062dc3eed8179.png
[4bd2300184834f98ac05c40911221282.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/23/0afb937f08dc49ae84f2d92300b18083.png
[5fcc6327830540928f0e8730e2f90a1d.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/23/79f5022dbc1c4caca7bd06923783e022.png
[2e75f826db7146559a3f707e14f18c05.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/23/057e3630ccba4c3daee020deca958bc1.png
[6b861a61a54448e7b89ac8ea98a0814f.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/23/398f84fd66504684b5bdf998e7b1ed42.png