【数据结构】优先级队列(堆)

💐1. 优先级队列

1.1 概念

队列是一种先进先出的数据结构，但是呢，有时候，数据之间也会有优先级，就比如说，我们想要拿到一个集合中的前k大的数据，或者是在平时，我们在打游戏时，这时候来电话了，但是，游戏也不能让他退出呀，这时候就会忽略掉电话，由此可见，游戏的优先级要比电话的优先级更高；

💐2.堆的概念及存储方式

优先级队列是由堆实现的， 而堆实际实际上是在完全二叉树的基础上进行了调整，而此时也就用到了 二叉树的顺序存储方式 这句话是什么意思呢？请看下图：

2.1 什么是堆

这里不做详细的介绍，只需知道，所有引用类型所创建的对象都保存在堆上，包括数组；而这里的堆是将所有的元素，按照完全二叉树的顺序存储方式存储到了一维数组中；

2.2 为什么要用完全二叉树描述堆呢？

2.3 为什么说堆是在完全二叉树的基础上进行的调整？

​ 堆又分为了大根堆和小根堆：

​ 从上图就可以发现两个性质：

​ 1.大根堆中，所有的父节点都比子节点大

​ 2.小根堆中，所有的父节点都比子节点小

2.4 使用数组还原完全二叉树

​ 在二叉树文章中，提到过这样一条性质：如果每一个节点都有一个编号 i 的话，那么：

1.当 i > 0 时，i 节点的父亲节点为: (i - 1) / 2;

2.如果 2i +1 < 节点的总数时，则下标为 i 节点的左孩子节点的下标为 2i + 1

3.如果 2i + 2 < 节点的总数时， 则下标为 i 的节点的左孩子节点的下标为 2i + 1

因为是在数组中进行存储的，所以完全二叉树中每一个节点的编号都是数组中每一个元素的下标；所以这样就可以使用数组来还原完全二叉树，然后再对完全二叉树进行调整；

在上一篇文章中，对于 优先级队列的概念及存储方式进行了一个详细的讲解，那么，本篇文章主要是针对优先级队列底层实现大致是什么样子的，亲手写一下代码结合图为大家讲解：

💐3. 堆的常用操作-模拟实现

3.1 堆的创建

我们知道，在上一篇文章中讲过，所有的元素都是在数组中存储的，那么，如何利用数组来实现 大根堆 和 小根堆的创建呢？就要考虑下面这个问题：

如果出现子节点比父节点大或者小该怎么办呢，怎么去调整呢？

3.1.1 堆的向下调整(大根堆为例)

可以看出，最后一棵子树的子节点比父节点大，我们所用的方法就是：

代码实现：

public class MyPriorityQueue {//底层数组private int[] element;//数组中的元素private int usedSize;//初始默认容量private static final int default_capacity = 9;public MyPriorityQueue(int[] arr) {this.element = new int[default_capacity];//传入一个数组，对element进行构造for(int i = 0; i<arr.length; i++) {element[i] = arr[i];usedSize++;}}//建一个大根堆public void buildHeap() {//parent 求出最后一棵子树的父亲节点for(int parent = (usedSize-2)/2; parent >= 0; parent--) {/*为什么减2而不是减1呢？因为，如果是最后一个节点的下标值，就是减一，但是，数组的长度值比下标大1，所以减2*///向下调整shiftDown(parent, usedSize);}}private void shiftDown(int parent, int len) {//求左孩子节点int child = (2*parent)+1;//判断是否有右孩子节点并且判断左孩子节点是否大于右孩子节点if(child+1 < len && element[child] < element[child+1]){//得到最大的孩子节点child++;}//判断孩子节点是否比父亲节点大if(element[child] > element[parent]) {//进行交换swap(parent, child);}}private void swap(int parent, int child) {int tmp = element[parent];element[parent] = element[child];element[child] = tmp;}public static void main(String[] args) {//测试用例int[] ele = {50, 45, 40, 20, 25, 35, 30, 10, 60};MyPriorityQueue myPriorityQueue = new MyPriorityQueue(ele);myPriorityQueue.buildHeap();}

但是，上述代码存在一个致命的问题：

代码优化：

    private void shiftDown(int parent, int len) {//求左孩子节点int child = (2*parent)+1;while(child < len) {//判断是否有右孩子节点并且判断左孩子节点是否大于右孩子节点if(child+1 < len && element[child] < element[child+1]){//得到最大的孩子节点child++;}//判断孩子节点是否比父亲节点大if(element[child] > element[parent]) {//进行交换swap(parent, child);//保证交换后，该树的子树仍然是大根堆parent = child;child = (2*parent)+1;}else {//表示以该节点为根的树已经是大根堆了break;}}}

3.1.2 建堆的时间复杂度

在学会了建堆以后，接下来就聊一聊建堆所用的复杂度吧！先说结论，最坏的情况是O(n),下面我来推到以下：

在推导之前先说明一下：因为堆是完全二叉树，而满二叉树也是完全二叉树，多几个节点也无所谓，时间复杂度本来就是一个近似值，所以为了容易理解，这里会用满二叉树进行推导

3.2 堆的插入和删除

3.2.1 堆的插入

堆的插入分为两个步骤：

1.将要添加的元素放在底层数组的最后一个位置；注意是否要扩容问题

2.向上调整该元素

下面讲解一下什么是向上调整

直接拿要添加的元素与根节点相比较，因为，本身已经是大根堆了，直接与根节点比较，符合条件就交换，不需要再与其他的节点比较

代码实现：

    //插入方法public void offer(int val) {//判断是否需要扩容if(is_full()) {this.element = Arrays.copyOf(element, element.length+1);}//向上调整this.element[usedSize] = val;shiftUp();usedSize++;}//向上调整private void shiftUp() {int parent = (usedSize-1)/2;int child = usedSize;while(child > 0) {if(element[parent] < element[child]) {swap(parent, child);}child = parent;parent = (child-1)/2;}}private boolean is_full() {return usedSize == element.length;}

3.2.2 堆的删除

1.将第一个元素和最后一个元素进行交换

2.节点实际上并没有被删除，而是节点的个数useSize减1

3.最后向上调整

代码实现

    //删除public void poll() {//排除空堆情况if(usedSize == 0) {return;}//交换第一个和最后一个元素swap(0,usedSize-1);//节点个数减1，不会对最后一个元素进行判断usedSize--;for(int parent = (usedSize-1)/2; parent >= 0; parent--) {//向下调整shiftDown(parent, usedSize);}}private void shiftDown(int parent, int len) {//求左孩子节点int child = (2*parent)+1;while(child < len) {//判断是否有右孩子节点并且判断左孩子节点是否大于右孩子节点if(child+1 < len && element[child] < element[child+1]){//得到最大的孩子节点child++;}//判断孩子节点是否比父亲节点大if(element[child] > element[parent]) {//进行交换swap(parent, child);//保证交换后，该树的子树仍然是大根堆parent = child;child = (2*parent)+1;}else {//表示以该节点为根的树已经是大根堆了break;}}}

💐4. PriorityQueue常用接口及特性

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

PriorityQueue的构造

构造器	功能讲解
PriorityQueue()	创建一个空的优先级队列，默认容量是11
PriorityQueue(int initialCapacity)	创建一个初始容量为intialCapacity的优先级队列，注意：initialCapacity不能小于1， 否则会抛出IllegalArgumentException异常
PriorityQueue(Collection<? extends E> c)	用一个集合来创建优先级队列
PriorityQueue(Comparator<? super E> comparator)	自定义类型进行比较，传入一个比较器

代码实现

   public static void main(String[] args) {//创建一个空的优先队列，底层默认容量是11PriorityQueue<Integer> priorityQueue1 = new PriorityQueue<>();//创建一个空的优先级队列，指定容量为100PriorityQueue<Integer> priorityQueue2 = new PriorityQueue<>(100);List<Integer> list = new ArrayList<>();list.add(1);list.add(2);list.add(3);//使用其他集合构造优先级队列PriorityQueue<Integer> priorityQueue3 = new PriorityQueue<>(list);//默认是小根堆，想要变成大根堆需要传入比较器PriorityQueue<Integer> priorityQueue4 = new PriorityQueue<>(new com());priorityQueue4.offer(1);priorityQueue4.offer(2);priorityQueue4.offer(3);}//定义一个比较器
class com implements Comparator<Integer> {@Overridepublic int compare(Integer o1, Integer o2) {return o2-o1;}
}

PriorityQueue使用时需要注意：

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

import java.until.PriorityQueue;

2. PriorityQueue中放置的元素必须要能够比较大小，不能插入不能比较大小的队象，否则会抛出ClassCastException异常
3. 不能插入 null对象， 否则会抛出NullPointerException
4. 没有容量限制，可以插入多个元素，其内部可以自动扩容
5. 插入和删除元素的时间复杂度为O(log2N)
6. PriorityQueue底层使用了堆数据结构
7. PriorityQueue默认情况下是小根堆

Java中提供的方法：

函数	功能介绍
boolean offer(E e)	插入元素e， 插入成功返回true，如果e为空，抛出异常，空间不够时会进行扩容
E peek()	获取优先级最高的元素，如果优先级队列为空，放回null
E pool()	移除优先级最高的元素，如果优先级队列为空，返回null
int size()	获取有效元素个数
void clear()	清空
boolean isEmpty()	检测优先级队列是否为空，如果为空返回true

优先级队列的扩容源码分析

💐5. PriorityQueue的比较方式

PriorityQueue底层使用堆结构，所以，内部的元素必须能够比较大小，PriorityQueue采用了：Comparble 和 Comjparator两种方式。

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

2. 也可以使用比较器，用户自己实现一个比较器类且实现Comaparator接口，并且让该类重写compare方法，指定根据对象的什么内容进行比较，然后再实例化PriorityQueue对象时，把比较器传进去；

源码讲解：

	//内部定义的比较器对象private final Comparator<? super E> comparator;//如果用户没有提供比较器，则使用内部的比较方式，将comparator置为nullpublic PriorityQueue() {this(DEFAULT_INITIAL_CAPACITY, null);}//如果用户提供了比较器，则采用提供的比较器进行比较public PriorityQueue(int initialCapacity,Comparator<? super E> comparator) {// Note: This restriction of at least one is not actually needed,// but continues for 1.5 compatibilityif (initialCapacity < 1)throw new IllegalArgumentException();this.queue = new Object[initialCapacity];this.comparator = comparator;}//在添加对象时进行向上调整//如果没有提供比较器，则采用内部比较方式，即Comparable//如果提供了比较器，则采用比较器进行比较private void siftUp(int k, E x) {if (comparator != null)siftUpUsingComparator(k, x);elsesiftUpComparable(k, x);}//采用comparable进行比较private void siftUpComparable(int k, E x) {Comparable<? super E> key = (Comparable<? super E>) x;while (k > 0) {int parent = (k - 1) >>> 1;Object e = queue[parent];if (key.compareTo((E) e) >= 0)break;queue[k] = e;k = parent;}queue[k] = key;}//采用comparator进行比较private void siftUpUsingComparator(int k, E x) {while (k > 0) {int parent = (k - 1) >>> 1;Object e = queue[parent];if (comparator.compare(x, (E) e) >= 0)break;queue[k] = e;k = parent;}queue[k] = x;}

💐6. 例子：使用优先级队列解决TOP-k问题

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

[面试题 17.14. 最小K个数 - 力扣（LeetCode）]()

class Solution {public int[] smallestK(int[] arr, int k) {//创建一个优先级队列PriorityQueue<Integer> heap = new PriorityQueue<>();//将所有元素加入到队列中for(int i = 0; i<arr.length; i++) {heap.add(arr[i]);}//创建一个数组用来存储前k个元素int[] ans = new int[k];//将堆中的前k个元素保存在数组中for(int i = 0; i<k; i++) {ans[i] = heap.poll();}//返回数组return ans;}
}

但是，上面这个代码只能针对于数据量较小时才行，如果数据量太大就会造成时间复杂度过高，比如，有一亿个数据，如果使用以上代码的话，会先将一亿个数据都保存在堆中，然后进行比较，这就得不偿失了；那么就要对代码进行一个优化：

1.用集合中的前k个元素建堆；

• 前k大个元素建小堆
• 前k小个元素建大堆

2.用剩余的n(元素的个数) - k个元素与堆中的元素进行比较；最后堆中剩余的元素就是前k个最大或最小的元素

代码实现：

    public int[] smallestK(int[] arr, int k) {//求前k个最小元素，所以要建大根堆，因为PriorityQueue默认的是小根堆，所以要传入比较器PriorityQueue<Integer> heap = new PriorityQueue<>(new Com());//将前k个元素加入到堆中for(int i = 0; i<k; i++){heap.add(arr[i]);}if(heap.isEmpty()) {return new int[]{};}//用剩余的元素与堆顶元素比较for(int i = k; i<arr.length; i++) {int x = heap.peek();//这里的条件语句求的是前k个最小元素if(arr[i] < x){heap.poll();heap.offer(arr[i]);}}int[] ans = new int[k];for(int i = 0; i<k; i++){ans[i] = heap.poll();}return ans;}
}
//自定义一个比较器
class Com implements Comparator<Integer> {@Overridepublic int compare(Integer o1, Integer o2) {return o2 - o1;}
}