数据结构之PriorityQueue源码及特性分析 (大小根堆转换、扩容)

Myth丶恋晨 2024-04-03 11:43 12阅读 0赞

## 文章目录 ##

*  一、**PriorityQueue****的特性**
 *  二、**PriorityQueue****常用接口介绍**
    
     *  1.**优先级队列的构造**
     *  2.**插入****/****删除****/****获取优先级最高的元素**
 *  三、**PriorityQueue源码分析**
 *   **1. 小跟堆源码分析**
 *   **2. PriorityQueue默认是小堆，如何变成大根堆呢？**
 *   **3. Integer数据类型是如何变成大根堆的？（自实现比较器）**
 *   **4. PriorityQueue扩容的源码分析**
 *  **四、总结**
 *  **五、****集合框架中****PriorityQueue****的比较方式**

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

###  ###

## 一、**PriorityQueue****的特性** ##

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

![c24c7205d0f94659b5d1095dbdca5d0e.png][]

**关于PriorityQueue的使用要注意：**

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

> import java.util.PriorityQueue;

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

public static void main(String[] args) {
            PriorityQueue<Student> priorityQueue = new PriorityQueue<>();
            priorityQueue.offer(new Student(10));
    
        }
    //这个时候虽然是不能比较的，但是此时运行也没有报错，那是因为此时只有一个对象，是不需要进行比较的

public static void main(String[] args) {
            PriorityQueue<Student> priorityQueue = new PriorityQueue<>();
            priorityQueue.offer(new Student(10));
            priorityQueue.offer(new Student(5));
    
        }
    //但是此时运行就会报错了，因为此时这两个对象是无法进行比较的

此时有两个解决办法，一个是给比较器，一个是实现Comparable接口并重写compareTo方法。

此时我们选择用实现Comparable接口并重写compareTo方法：

class Student implements Comparable<Student>{
        public int age;
        public Student(int age){
            this.age = age;
        }
    
        @Override
        public int compareTo(Student o) {
            return this.age - o.age;
        }
    }

**3. 不能插入null对象，否则会抛出NullPointerException  
4. 没有容量限制，可以插入任意多个元素，其内部可以自动扩容  
5. 插入和删除元素的时间复杂度为O(log2N)(log以2为底的N）  
6. PriorityQueue底层使用了堆数据结构  
7. PriorityQueue默认情况下是小堆---即每次获取到的元素都是最小的元素**

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

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

<table style="width:500px;"> 
 <tbody> 
  <tr> 
   <td>构造器</td> 
   <td>功能介绍</td> 
  </tr> 
  <tr> 
   <td>PriorityQueue()</td> 
   <td>创建一个空的优先级队列，默认容量是11</td> 
  </tr> 
  <tr> 
   <td>PriorityQueue(int<br> initialCapacity)</td> 
   <td>创建一个初始容量为initialCapacity的优先级队列，注意：<br> initialCapacity不能小于1，否则会抛IllegalArgumentException异<br> 常</td> 
  </tr> 
  <tr> 
   <td>PriorityQueue(Collection&lt;?<br> extends E&gt; c)</td> 
   <td>用一个集合来创建优先级队列</td> 
  </tr> 
 </tbody> 
</table>

2.**插入****/****删除****/****获取优先级最高的元素**

<table style="width:500px;"> 
 <tbody> 
  <tr> 
   <td>函数名</td> 
   <td>功能介绍</td> 
  </tr> 
  <tr> 
   <td>boolean<br> offer(E e)</td> 
   <td>插入元素e，插入成功返回true，如果e对象为空，抛出NullPointerException异常，时间复杂度O(log2N)(log以2为底的N），注意：空间不够时候会进行扩容</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>boolean<br> isEmpty()</td> 
   <td>检测优先级队列是否为空，空返回true</td> 
  </tr> 
 </tbody> 
</table>

### 三、**PriorityQueue源码分析** ###

**1.针对一下三行做源码分析（小根堆）：**

PriorityQueue<Student> priorityQueue = new PriorityQueue<>();
            priorityQueue.offer(new Student(10));
            priorityQueue.offer(new Student(5));

>     PriorityQueue<Student> priorityQueue = new PriorityQueue<>();
> 
> 这一行代码的源码分析如下：

![aa68400e6f7046159f7d2cfe03143996.png][]

>     priorityQueue.offer(new Student(10));
> 
> 接下来我们看**第一次offer 的源码：**

![ff8035cd368e459890a694a20fdc12e1.png][]

> priorityQueue.offer(new Student(5));
> 
> 接下来我们看**第二次offer的源码：**

![09a634b6af0e48898d848276f01293eb.png][]

**2. PriorityQueue默认是小根堆，如何变成大根堆呢？**

可以通过修改比较规则，就可以变成大根堆。

有两种方式：

一是，通过上面我们的源码分析，可以修改比较规则，可以修改成为 < ;但是源码我们是修改不了的，那么我直接看第二中方式。

![533051bc9f1244f3a983f216d7e49654.png][]

二是：在重写的comparaTo方法里面修改比较规则：

public int compareTo(Student o) {
            return this.age - o.age;
        }

![7005ca96ac394b48a1a955b4c8f6f496.png][]  **3. Integer数据类型是如何变成大根堆的？（自实现比较器）**

**第一步，先自实现比较器：**

class IntComparator implements Comparator<Integer>{
    
        @Override
        public int compare(Integer o1, Integer o2) {
            //return o2 - o1;
            return o2.compareTo(o1);
        }
    }

**第二步，传参的时候传入比较器：**

PriorityQueue<Integer> priorityQueue = new PriorityQueue<>(new IntComparator());

###  ###

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

此时我们再次运行程序，就已经是大根堆了。

下面我们进行源码分析：

![cb9d20d70ea04cc3a812886a294da08c.png][]

**4. PriorityQueue扩容的源码分析**

private void grow(int minCapacity) {
            int oldCapacity = queue.length;
            // Double size if small; else grow by 50%
            int newCapacity = oldCapacity + ((oldCapacity < 64) ?
                                             (oldCapacity + 2) :
                                             (oldCapacity >> 1));
            // overflow-conscious code
            if (newCapacity - MAX_ARRAY_SIZE > 0)
                newCapacity = hugeCapacity(minCapacity);
            queue = Arrays.copyOf(queue, newCapacity);
        }

**如果容量小于64时，是按照oldCapacity的2倍方式扩容的  
如果容量大于等于64，是按照oldCapacity的1.5倍方式扩容的  
如果容量超过MAX\_ARRAY\_SIZE（2147483639），按照MAX\_ARRAY\_SIZE来进行扩容**

![9f01decc0d5d4faf971bcf09c250bdc7.png][]

## 4 总结 ##

**1.当没有传入数组容量的时候，默认是11**

**2.当没有传入比较器的时候，传入的对象必须是可比较的，不然会报错**

**3.优先使用的是比较器来比较**

### **5** **集合框架中****PriorityQueue****的比较方式** ###

集合框架中的PriorityQueue底层使用堆结构，因此其内部的元素必须要能够比大小，PriorityQueue采用了： Comparble和Comparator两种方式。

1. Comparble是默认的内部比较方式，如果用户插入自定义类型对象时，该类对象必须要实现Comparble接口，并覆写compareTo方法

2. 用户也可以选择使用比较器对象，如果用户插入自定义类型对象时，必须要提供一个比较器类，让该类实现 Comparator接口并覆写compare方法。

以下有三种比较方式的对比：

<table style="width:500px;"> 
 <tbody> 
  <tr> 
   <td>重写的方法</td> 
   <td>说明解释</td> 
  </tr> 
  <tr> 
   <td> 
    <div>
      Object.equals 
    </div> </td> 
   <td> 
    <div>
      因为所有类都是继承自 Object 的，所以直接覆写即可，不过只能比较相等与 
    </div> 
    <div>
      否 
    </div> </td> 
  </tr> 
  <tr> 
   <td> 
    <div>
      Comparable.compareTo 
    </div> </td> 
   <td> 
    <div>
      需要手动实现接口，侵入性比较强，但一旦实现，每次用该类都有顺序，属于内部顺序 
    </div> </td> 
  </tr> 
  <tr> 
   <td> 
    <div>
      Comparator.compare 
    </div> </td> 
   <td>需要实现一个比较器对象，对待比较类的侵入性弱，但对算法代码实现侵入性强</td> 
  </tr> 
 </tbody> 
</table>

[c24c7205d0f94659b5d1095dbdca5d0e.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/03/7ce1111fb2424972a8ca6f1b7d25c991.png
[aa68400e6f7046159f7d2cfe03143996.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/03/9f9f2494360a4413951f9a7965b0c504.png
[ff8035cd368e459890a694a20fdc12e1.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/03/49c9c05b0bdb49c0830d34b2a5cc8e5d.png
[09a634b6af0e48898d848276f01293eb.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/03/7779f52abfba4000922e647e28f61255.png
[533051bc9f1244f3a983f216d7e49654.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/03/40a261338d4142ffbd67c50c8c1cc1ee.png
[7005ca96ac394b48a1a955b4c8f6f496.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/03/89c058ad9cbc4e1a8b86da42f445f5a8.png
[cb9d20d70ea04cc3a812886a294da08c.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/03/511c1e71a14f4469a6eaf7474e1f69c4.png
[9f01decc0d5d4faf971bcf09c250bdc7.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/03/31cc3087d4dc4aed80a0d6a2344cd641.png