优先级队列 ( PriorityQueue )

文章目录

前言
一、优先级队列
- 1.1、概念
二、优先级队列的模拟实现
- 2.1、堆的概念
- 2.2、堆的存储方式
- 2.3、堆的创建
- 2.4、堆的插入与删除
三、常用接口介绍
- 3.1、Top-k问题
- 3.2、使用PriorityQueue创建大小堆，解决TOPK问题

前言

前几篇我们讲解过队列，其是一种先进先出（FIFO）的数据结构，但在某些特殊情况下，我们操作的数据可能拥有优先级，在出队列时需要优先级高的数据先出。比如排队检票时，我们经常看到“军人优先”；或者我们在电脑玩游戏时，如果有电话打过来，我们会先处理未接电话。在此情况下使用队列显然很不合适。那么我们就要引入优先级队列（堆）。

一、优先级队列

1.1、概念

提供返回最高优先级对象和添加新的对象的两个最基本的操作的数据结构就是优先级队列(Priority Queue)。

二、优先级队列的模拟实现

2.1、堆的概念

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

堆的性质：

$\,$ $\square$ $\,$ 堆中某个节点的值总是不大于或不小于其父节点的值；

$\square$ 堆总是一棵完全二叉树。

2.2、堆的存储方式

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

注意：对于非完全二叉树，则不适合使用顺序方式进行存储，因为为了能够还原二叉树，空间中必须要存储空节点，就会导致空间利用率比较低。

将元素存储到数组中后，可以根据二叉树章节的性质5对树进行还原。假设i为节点在数组中的下标，则有：

$\bullet$ 如果 i 为0，则i表示的节点为根节点，否则i节点的双亲节点为 (i - 1) / 2

$\bullet$ 如果2 * i + 1 小于节点个数，则节点i的左孩子下标为2 * i + 1，否则没有左孩子

$\bullet$ 如果2 * i + 2 小于节点个数，则节点i的右孩子下标为2 * i + 2，否则没有右孩子

2.3、堆的创建

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

2.3.1、堆的向下调整

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

向下过程(以小堆为例)：

1. 让parent标记需要调整的节点，child标记parent的左孩子(注意：parent如果有孩子一定先是有左孩子)

2. 如果parent的左孩子存在，即:child < size，进行以下操作，直到parent的左孩子不存在

   $\bullet$ parent右孩子是否存在，存在找到左右孩子中最小的孩子，让child进行标记

         $\bullet$ 将parent与较小的孩子child比较，如果：

                 $\bullet$   parent小于较小的孩子child，调整结束

                 $\bullet$ 否则：交换parent与较小的孩子child，交换完成之后，parent中大的元素向下移动，可能导致子树不满足对的性质，因此需要继续向下调整，即 parent = child；child = parent*2+1; 然后继续第2步。

public class Heap {public int[] arr;public int usedSize=0;public Heap(){this.arr=new int[10];}public void initHeap(int[] array){for (int i = 0; i < arr.length; i++) {this.arr[i]= array[i];this.usedSize++;}}public void siftDown(int parent,int usedSize){int child=parent*2+1;while(child<usedSize){if(child+1<usedSize&&arr[child]<arr[child+1]){child++;}if(arr[child]>arr[parent]){int tmp=arr[child];arr[child]=arr[parent];arr[parent]=tmp;parent=child;child=2*parent+1;}else{break;}}}

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

2.3.2、堆的创建

对于普通的序列{1，5，3，8，7，6}，左右子树不满足堆的特性，如何创建堆呢？

代码如下：

public void createHeap(){for (int parent = (this.usedSize-1-1)/2; parent >= 0; parent--) {siftDown(parent,this.usedSize);}}

2.4、堆的插入与删除

2.4.1、堆的插入

堆的插入总共需要两个步骤：

1. 先将元素放入到底层空间中(注意：空间不够时需要扩容)

2. 将最后新插入的节点向上调整，直到满足堆的性质

例如插入“10” 元素，先放在堆的底部，然后进行调整：

 public void push(int val){if(isFull()){arr=Arrays.copyOf(arr,arr.length*2);}arr[usedSize]=val;siftUp(usedSize);this.usedSize++;}public boolean isFull(){return this.usedSize==arr.length;}

2.4.2、堆的删除

注意：堆的删除一定删除的是堆顶元素。

具体如下：

1. 将堆顶元素和堆中最后一个元素交换

2. 将堆中有效数据个数减少一个

3. 对堆顶元素进行向下调整

三、堆的应用

3.1、Top-k问题

TOP-K问题：即求数据集合中前K个最大的元素或者最小的元素，一般情况下数据量都比较大。

比如：专业前10名、世界500强、富豪榜、游戏中前100的活跃玩家等。

对于Top-K问题，能想到的最简单直接的方式就是排序，但是：如果数据量非常大，排序就不太麻烦了(可能数据都不能一下子全部加载到内存中)。最佳的方式就是用堆来解决，基本思路如下：

        1. 用数据集合中前K个元素来建堆

          $\bullet$   前k个最大的元素，则建小堆

          $\bullet$   前k个最小的元素，则建大堆

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

最小K个数https://leetcode.cn/problems/smallest-k-lcci/description/解题代码：

class IntCmp implements Comparator<Integer>{public int compare(Integer o1,Integer o2){return o2.compareTo(o1);}
}
class Solution {public int[] smallestK(int[] arr, int k) {PriorityQueue<Integer> priorityQueue=new PriorityQueue<>(new IntCmp());int[] ret=new int[k];if(arr==null||k==0){return ret;}for(int i=0;i<k;i++){priorityQueue.offer(arr[i]);}for(int j=k;j<arr.length;j++){int val=priorityQueue.peek();if(val>arr[j]){priorityQueue.poll();priorityQueue.offer(arr[j]);}}for(int i=0;i<k;i++){ret[i]=priorityQueue.poll();}return ret;}
}

3.2、使用PriorityQueue创建大小堆，解决TOPK问题

//使用比较器创建小根堆
class LessIntComp implements Comparator<Integer>{@Overridepublic int compare(Integer o1, Integer o2) {return o1 - o2;}
}
//使用比较器创建大根堆
class GreaterIntComp implements Comparator<Integer>{@Overridepublic int compare(Integer o1, Integer o2) {return o2 - o1;}
}
public class TestDemo<E> {//求最小的K个数，通过比较器创建大根堆public static int[] smallestK(int[] array, int k) {if(k <= 0) {return new int[k];}GreaterIntComp greaterCmp = new GreaterIntComp();PriorityQueue<Integer> maxHeap = new PriorityQueue<>(greaterCmp);
//先将前K个元素，创建大根堆for(int i = 0; i < k; i++) {maxHeap.offer(array[i]);}
//从第K+1个元素开始，每次和堆顶元素比较for (int i = k; i < array.length; i++) {int top = maxHeap.peek();if(array[i] < top) {maxHeap.poll();maxHeap.offer(array[i]);}}
//取出前K个int[] ret = new int[k];for (int i = 0; i < k; i++) {int val = maxHeap.poll();ret[i] = val;}return ret;}public static void main(String[] args) {int[] array = {4,1,9,2,8,0,7,3,6,5};int[] ret = smallestK(array,3);System.out.println(Arrays.toString(ret));}
}