掌握优先级队列：提升效率的关键技巧

ゝ一纸荒年。 2024-02-22 09:29 64阅读 0赞

#### 目录 ####

*  优先级队列的概念
 *  优先级队列的模拟实现
 *   *  堆的创建
     *  堆的插入与删除
     *   *  堆的插入
         *  堆的删除
     *  用堆模拟实现优先级队列
 *  常见接口了解
 *   *  PriorityQueue的几种常见构造方法

## 优先级队列的概念 ##

队列是一种先进先出的数据结构，但在一些情况下我们要优先处理一些情况，比如：正在手机上打游戏的时候，如果有来电，那么系统就应该处理打进来的电话。  
在这种情况下，数据结构应该提供两个最基本的操作，一个是返回最高优先级对象，一个是添加新的对象。这种数据结构就是优先级队列(Priority Queue)。  
![在这里插入图片描述][ad38728c6cbd47f091ed83aca2ea6333.png]

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

DK1.8中的PriorityQueue底层使用了堆这种数据结构，而堆实际就是在完全二叉树的基础上进行了一些调整。因此我们先来模拟堆的创建，插入与删除。

### 堆的创建 ###

堆的创建代码：

//找倒数第一个非叶子节点，从该节点位置开始往前一直到根节点,遇到一个节点就使用向下调整
        public  void  creatHeap(int[] arr){
        
        int root = (arr.length-2)/2;
            for (; root>=0 ; root--) {
        
                shiftDown(arr,root);
            }
        }

建堆的时间复杂度为O(N)  
堆的向下调整代码（以创建大堆代码为例）：

public void shiftDown(int[] arr, int parent){
        
            // child先标记parent的左孩子，因为parent可能右左没有右
        int child = parent*2+1;
        int size = arr.length;
        while (child < size){
        
            // 如果右孩子存在，找到左右孩子中较大的孩子,用child进行标记
            if(child+1 < size && arr[child] < arr[child+1]){
        
                child++;
            }
            // 如果双亲比其最大的孩子还小，则交换
            if(arr[child]>parent){
        
                int temp = arr[child];
                arr[child] = arr[parent];
                arr[parent] = temp;
            }else {
        
                break;
            }
            parent = child;
            child = (parent*2)+1;
        }
        }

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

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

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

public void push(int val) {
        
          if(isFull()){
        
              return;
          }
          //usedSize为堆中元素个数
          elem[usedSize]=val;
          usedSize++;
          shiftUp(usedSize-1);
        }

向上调整：

private void shiftUp(int child){
        
            // 找到child的双亲
            int parent = (child-1)/2;
            while (parent >= 0){
        
                if(arr[parent]>=arr[child]){
        
                    break;
                }else {
        
                    // 将双亲与孩子节点进行交换
                    int temp = arr[parent];
                    arr[parent] = arr[child];
                    arr[child] = temp;
                    child = parent;
                    parent = (child-1)/2;
                }
            }
        }

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

> 堆的删除一定删除的是堆顶元素。具体如下：
> 
> 1.  将堆顶元素对堆中最后一个元素交换
> 2.  将堆中有效数据个数减少一个
> 3.  对堆顶元素进行向下调整

public void pollHeap() {
        
            if(isEmpty()){
        
                return;
            }
            elem[0] = elem[usedSize-1];
            usedSize--;
            shiftDown(0,usedSize);
        }

### 用堆模拟实现优先级队列 ###

public class MyPriorityQueue {
         
     private int[] array = new int[100];   
     private int size = 0;
     //入队
     public void offer(int e) {
        
     array[size++] = e;
     //向上调整
     shiftUp(size - 1);
     }
     //出队
     public int poll() {
        
     int oldValue = array[0];
     array[0] = array[--size];
     //向下调整
     shiftDown(0);
     return oldValue;
     }
     //出堆首元素
     public int peek() {
        
     return array[0];
     }
     }

## 常见接口了解 ##

Java集合框架中提供了PriorityQueue和PriorityBlockingQueue两种类型的优先级队列，PriorityQueue是线程不安全的，PriorityBlockingQueue是线程安全的。  
关于PriorityQueue的使用要注意：

1.  使用时必须导入PriorityQueue所在的包
2.  PriorityQueue中放置的元素必须要能够比较大小，不能插入无法比较大小的对象，否则会抛出ClassCastException异常
3.  不能插入null对象，否则会抛出NullPointerException
4.  没有容量限制，可以插入任意多个元素，其内部可以自动扩容
5.  插入和删除元素的时间复杂度为O（logN）
6.  PriorityQueue底层使用了堆数据结构
7.  PriorityQueue默认情况下是小堆-即每次获取到的元素都是最小的元素

### PriorityQueue的几种常见构造方法 ###

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

我们可以使用优先级队列解决一些问题，例如TOPK问题：最大或者最小的前k个数据。  
思路就是我们求最大的前k个数据，我们用数据的前k个数字建一个小堆，然后依次拿堆顶元素与剩下的数据进行比较，如果那个数据大于堆定元素就进行互换，直到遍历完剩下的数据，堆中k个数据就为最大的k个数据。堆顶元素就为第k大元素。  
总结思路就是：

1.  用数据集合中前K个元素来建堆  
    前k个最大的元素，则建小堆  
    前k个最小的元素，则建大堆
2.  用剩余的N-K个元素依次与堆顶元素来比较，不满足则替换堆顶元素  
    将剩余N-K个元素依次与堆顶元素比完之后，堆中剩余的K个元素就是所求的前K个最小或者最大的元素。

[ad38728c6cbd47f091ed83aca2ea6333.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/22/7410f59b474d40f9ae3ecca31fe29971.png