优先级队列（堆）

灰太狼 2024-02-22 09:32 55阅读 0赞

## 优先级队列 ##

### 概念 ###

> 我们知道，**队列是一种先进先出的数据结构**，但有些情况下，**操作的数据可能带有优先级，一般出队列时，可能需要优先级高的元素先出队列**，该中场景下，使用队列显然不合适，比如在使用手机玩游戏的时候，如果有来电，那么系统应该优先处理打进来的电话；有的班主任可能会让成绩好的同学先挑选座位。
> 
> 在此类情况下，数据结构应该提供两个最基本的操作，**一个是返回最高优先级对象，一个是添加新的对象**。这种数据结构就是优先级队列。

## 优先级队列的模拟实现 ##

JDK1.8中的PriorityQueue底层使用了堆这种数据结构，而堆实际上是在完全二叉树的基础上进行了一些调整。

### 堆的概念 ###

> 如果有一个关键码的集合K = \{k0, k1, k2,... kn-1\},把它的所有元素**按完全二叉树的顺序存储方式存储在一个一维数组当中**，并满足ki <= k2i + 1 且 ki <= k2i + 2(ki >= k2i + 1 且 ki > k2i + 2), i = 0, 1,....,则称为小堆（或大堆）。将根节点最大的堆叫做最大堆或者大根堆，根节点最小的堆叫做最小堆或者小根堆。

**堆的性质：  
1.堆中某个结点的值总是不小于或者不大于父节点的值；**

**2.堆总是一棵完全二叉树。**

![55610b7843da4ec480f4b15f4daf7364.png][]

### 堆的存储方式 ###

从堆的概念可知，堆是一棵完全二叉树，因此**可以层序的规则采用顺序的方式来高效存储**。

> 将元素存储到数组中后，可以利用以下性质对树进行还原。假设i为结点在数组中下标，则有：
> 
> 1.如果i为0，则i表示的节点为根节点，否则i结点的双亲结点为(i-1)/2.
> 
> 2.如果2 \* i + 1小于节点个数，则结点i的左孩子下标为2 \* i + 1,否则没有左孩子
> 
> 3.如果2 \* i + 2小于节点个数，则结点i的右孩子下标为2 \* i + 2,否则没有右孩子

#### 堆的创建 ####

#### 堆向下调整 ####

对于集合\{27, 15, 19, 18, 28, 34, 65, 49, 25, 37\}中的数据，如何将其创建成小根堆呢？

![9884f083336d42d9859493bc10e53bfc.png][]

观察上图后发现：根结点的左右子树已经完全满足堆的性质，因此只需将根结点向下调整好即可。

**向下调整的过程（以小堆为例）：**

> 1. **让parent标记需要调整的结点，child标记parent的左孩子**(注意：parent如果有孩子一定是先有的左孩子)
> 
> 2.**如果parent的左孩子存在，即:child < size(完全二叉树的大小),进行以下操作，直到parent的左孩子不存在**。
> 
> （1）判断parent的右孩子是否存在，存在找到左右孩子中最小的孩子，让child进行标记
> 
> （2）将parent与较小的孩子进行比较，如果：parent小于较小的孩子child，调整结束；否则：交换parent与较小的孩子child，交换完成后，parent中大的元素向下移动，可能导致子树不满足对的性质，因此需要继续向下调整，即:parent = child; child = 2\*parent+1,后继续2.

![0d717cd768754ec98f7b2abb630d2f62.png][]

具体代码如下：

public void shiftDown(int[] array, int parent) {
            //child先标记parent的左孩子，因为parent可能有左没有右
            int child = 2 * parent + 1;
            int size = array.length;
    
            while(child < size) {
                //如果右孩子存在，找到左右孩子中较小的孩子，用child进行标记
                if(child + 1 < size && array[child + 1] < array[child]) {
                    child++;
                }
    
                //如果双亲比其最小的孩子还小，说明该结构已经满足堆的特性了
                if(array[parent] <= array[child]) {
                    break;
                } else {
                    //将双亲与较小的孩子交换
                    int t = array[parent];
                    array[parent] = array[child];
                    array[child] = t;
    
                    //parent中大的元素往下移动，可能会造成子树不满足堆的性质，因此需要继续向下调整
                    parent = child;
                    child = 2 * parent + 1;
                }
            }
        }

**注意：在调整以parent为根的二叉树时，必须要满足parent的左子树和右子树已经是堆了才可以向下调整。**

**时间复杂度分析：最坏的情况即如图所示的情况，从根一路比较到叶子，比较的次数为完全二叉树的高度，即时间复杂度为O(log2 n)**

#### 堆的创建 ####

那对于普通的序列\{1,5,3,8,7,6\},即根结点的左右子树都不满足堆的特性，又该如何调整呢？

![70706591319b43669bb28ecdef30d3be.png][]

参考代码：

public static void createHeap(int[] array) {
            //调整方法：找倒数第一个非叶子结点，从该节点位置开始往前一直到根结点，遇到一个结点，应用向下调整
            int root = ((array.length - 2) >> 1);
            for(; root >= 0; root--) {
                shiftDown(array, root);
            }
        }

**最终的时间复杂度：O(n),可自行进行推导。**

### **堆的插入与删除** ###

#### **堆的插入** ####

> **堆的插入总共需要两个步骤：**
> 
> 1.先将元素放入到底层空间中（注：空间不够时需要扩容）
> 
> 2.将最后新插入的结点**向上调整**，直到满足堆的性质。

![0f1aa04dfb9742679fcd8a0a47ca1b4e.png][]

与向下调整类似，让我们先来看一下向上调整的代码。

public void shiftUp(int array[], int child) {
            //找到child的双亲
            int parent = (child - 1) / 2;
    
            while(child > 0) {
                //如果双亲比孩子小，parent满足堆的性质，调整结束
                if(array[parent] < array[child]) {
                    break;
                } else {
                    //将双亲与孩子结点进行交换
                    int t = array[parent];
                    array[parent] = array[child];
                    array[child] = t;
                    
                    //小的元素向下移动，可能到值子树不满足对的性质，因此需要继续向上调增
                    child = parent;
                    parent = (child - 1) / 2;
                }
            }
        }

#### 堆的删除 ####

**注意：堆的删除一定删除的是堆顶元素。具体如下：**

> 1.将堆顶元素对堆中最后一个元素交换
> 
> 2.将堆中有效数据的个数减少一个
> 
> 3.对堆顶元素向下调整

![d242338a97a94d2ab6177e258961c805.png][]

代码也很简单 ：

public static void poll(int[] array, int size) {
            //交换顶和末元素,size为当前数组大小
            int tmp = array[0];
            array[0] = array[--size];
            array[--size] = array[0];
            
            shiftDown(array, array[0]);
        }

## 常用接口介绍 ##

### PriorityQueue的特性 ###

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

关于PriorityQueue的使用要注意：  
1.使用时必须导入PriorityQueue所在的包，即：

> import java.util.PriorityQueue;

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

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

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

5.**插入和删除元素的时间复杂度为O(log2 n)**

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

7.**Priority默认情况下是小堆，即每次获得到的元素都是最小的元素**

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

> 1.优先级队列的构造
> 
> 此处只是列出了PriorityQueue中几种常见的构造方式，其它的可以借助Api查询

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

举个例子简要介绍一下它的构造：

public static void TestPriorityQueue() {
            //创建一个空的优先级队列，底层默认容量是11
            PriorityQueue<Integer> q1 = new PriorityQueue<>();
    
            //创建一个空的优先级队列，底层的容量为initalCapacity
            PriorityQueue<Integer> q2 = new PriorityQueue<>(100);
    
            ArrayList<Integer> list = new ArrayList<>();
            list.add(4);
            list.add(3);
            list.add(2);
            list.add(1);
    
            //用ArrayList对象来构造一个优先级队列的对象
            PriorityQueue<Integer> q3 = new PriorityQueue<>(list);
            System.out.println(q3.size());
            System.out.println(q3.peek());
        }

注意：默认情况下，PriorityQueue队列是小堆，如果需要大堆需要用户提供的比较器

代码样例如下：

static class IntCmp implements Comparator<Integer> {
         @Override
         public int compare(Integer o1, Integer o2) {
            return o2 - o1;//这里的比较使最终创建结果为大根堆
         }
    }
    
    
     public static void main(String[] args) {
            //表明该优先级队列使用的是用户自己提供的比较器
            PriorityQueue<Integer> p = new PriorityQueue<>(new IntCmp());
            p.offer(4);
            p.offer(3);
            p.offer(2);
            p.offer(1);
    
            p.offer(5);
            System.out.println(p.peek());
        }

此时创建出的就是一个大堆。

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

<table style="width:700px;"> 
 <tbody> 
  <tr> 
   <td><strong>函数名</strong></td> 
   <td><strong>功能介绍</strong></td> 
  </tr> 
  <tr> 
   <td>boolean offer(E e)</td> 
   <td>插入元素e，插入成功返回true，如果e对象为空，则抛出NullPointerException异常，时间复杂度为O(log2 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 clear()</td> 
   <td>清空</td> 
  </tr> 
  <tr> 
   <td>boolean isEmpty()</td> 
   <td>检测优先级队列是否为空，空返回true</td> 
  </tr> 
 </tbody> 
</table>

代码示例如下：

public static void TestPriorityQueue2() {
            int arr[] = {4, 1, 9, 2, 8, 0, 7, 3, 6, 5};
    
            //一般在创建优先级队列对象时，如果知道元素个数，建议就直接将底层容量给好
            //否则在插入当中不断需要扩容
            //扩容机制：开辟更大的空间，拷贝元素，这样效率会比较低
            PriorityQueue<Integer> q = new PriorityQueue<>(arr.length);
            for(int e : arr) {
                q.offer(e);
            }
    
            System.out.println(q.size());
            System.out.println(q.peek());
    
            //从优先级队列中删除连个元素之和，再次获取优先级最高的元素
            q.poll();
            q.poll();
            System.out.println(q.size());
            System.out.println(q.peek());
            
            q.offer(0);
            System.out.println(q.peek());
            
            //将优先级队列中的有效元素删除掉，检测其是否为空
            q.clear();
            if(q.isEmpty()) {
                System.out.println("优先级队列已经为空！！！");
            } else {
                System.out.println("优先级队列不为空");
            }
        }

注意：以下是JDK1.8当中，PriorityQueue的扩容方式：

privatestaticﬁnalintMAX_ARRAY_SIZE=Integer.MAX_VALUE-8;
    
    privatevoidgrow(intminCapacity){
     intoldCapacity=queue.length;
      //Doublesizeifsmall; elsegrowby50%
      intnewCapacity=oldCapacity+((oldCapacity<64)?
                      (oldCapacity+2):
                      (oldCapacity>>1));
      //overﬂow-consciouscode
      if(newCapacity-MAX_ARRAY_SIZE>0)
        newCapacity=hugeCapacity(minCapacity);
      queue=Arrays.copyOf(queue,newCapacity);
    }
    
    privatestaticinthugeCapacity(intminCapacity){
     if(minCapacity<0)//overﬂow
        thrownewOutOfMemoryError();
      return(minCapacity>MAX_ARRAY_SIZE)?
        Integer.MAX_VALUE:
        MAX_ARRAY_SIZE;
    }

> 优先级队列的扩容说明：
> 
> 1.如果容量小于64时，是按照oldCapacity的2倍方式扩容的
> 
> 2.如果容量大于等于64， 是按照oldCapacity的1.5倍方式扩容的
> 
> 3.如果容量超过MAX\_ARRAY\_SIZE,按照MAX\_ARRAY\_SIZE来进行扩容

[55610b7843da4ec480f4b15f4daf7364.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/22/f3ac0ae252874c1ea22b62af7b5cef55.png
[9884f083336d42d9859493bc10e53bfc.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/22/59e66a875fde4f15a7e3aeb614b88a5c.png
[0d717cd768754ec98f7b2abb630d2f62.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/22/f62a7f6f857d4450bf823d78d826a8cb.png
[70706591319b43669bb28ecdef30d3be.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/22/cb73b79bd4e94eddbbc35782896698a9.png
[0f1aa04dfb9742679fcd8a0a47ca1b4e.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/22/22a09dbe15764e75850ac1a4ed621ce4.png
[d242338a97a94d2ab6177e258961c805.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/22/2b6129d121a9451f9f97cd054c775a3e.png