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

目录

1. 优先级队列（堆）​编辑

1.1 概念

2. 优先级队列的模拟实现

2.1 堆(Heap)的概念

2.2 堆的性质

2.3 堆的存储方式

2.4 堆的创建

2.4.1 堆向下调整 

2.4.2 建堆的时间复杂度 O(N)

2.5 堆的插入与删除

2.5.1 堆的插入（向上调整方式）

2.5.2 向上调整建堆的时间复杂度

【小结】

2.5.3 堆的删除

3. 常用接口介绍

3.1 PriorityQueue的特性

3.2 PriorityQueue常用方法介绍

3.2.1 优先级队列的构造

3.2.2 PriorityQueue构造大根堆

【小结】

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

3.2.4 扩容方式（PriorityQueue）

TOP - K 问题   O(N*logK)

堆排序   O(N*logN)

---

1. 优先级队列（堆）

• PriorityQueue优先级队列，实现了Queue接口
• 优先级队列(概念...)，底层实现是一个完全二叉树。
• 为了体现队列中元素的优先级性，把这个完全二叉树看成堆，堆又分为大根堆和小根堆。
• 即PriorityQueue 要么是大根堆，要么是小根堆。

1.1 概念

前面介绍过队列，队列是一种先进先出(FIFO)的数据结构，但有些情况下，操作的数据可能带有优先级，一般出队列时，可能需要优先级高的元素先出队列，该中场景下，使用队列显然不合适，比如：在手机上玩游戏的时候，如果有来电，那么系统应该优先处理打进来的电话；初中那会班主任排座位时可能会让成绩好的同学先挑座位。

在这种情况下，数据结构应该提供两个最基本的操作，一个是返回最高优先级对象，一个是添加新的对象。这种数据结构就是优先级队列(Priority Queue)

2. 优先级队列的模拟实现

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

2.1 堆(Heap)的概念

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

2.2 堆的性质

2.3 堆的存储方式

从堆的概念可知，堆是一棵完全二叉树，因此可以按照层序遍历采用顺序的方式来高效存储。即数组中存储的是层序遍历的结果。

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

• 如果 i 为0，则 i 表示的节点为根节点，否则 i 节点的双亲节点为 (i - 1)/2  向下取整
• 如果2 * i + 1 小于节点个数，则节点 i 有左孩子 序号为：2i+1，否则无左孩子
• 如果2 * i + 2 小于节点个数，则节点 i 有右孩子 序号为：2i+2，否则无右孩子

2.4 堆的创建

2.4.1 堆向下调整 

对于集合{ 27,15,19,18,28,34,65,49,25,37 }中的数据，实现代码将其创建成堆（优先级队列）

先将上面的数组集合，手动创建为大根堆：

总结一下调整的过程:

1. 从最后一棵子树开始调整的(非叶子节点)
2. 找到左右孩子的最大值和根节点进行比较，如果比根节点大，那么就交换。即向下调整，向下调整是每棵树的父节点向下移动。
3. 如果能够知道子树的根节点下标，那么下一棵子树就是当前根节点下标 -1
4. 一直调整到0下标这棵树停止。即把每课树都向下调整为大根堆。

向下调整这种方式，时间复杂度为：树的高度，O()

对这个堆的增删改等所有操作之后，都要满足最后它还是一个大根堆。

直接从这棵树的根节点向下调整是不行的，因为这样调整一遍不一定调整为大根堆，可以画图看一下。

问题:

1. 每棵子树调整的时候结束的位置怎么定：length(数组的长度)
2. 最后一棵子树的根节点下标怎么定：   (i - 1)/2  -》  i = length - 1

堆的创建以及向下调整过程： 

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

public class TestHeap {public int[] elem;public int usedSize;//记录当前堆当中 有效的数据个数public static final int DEFAULT_CAPACITY = 10;public TestHeap() {this.elem = new int[DEFAULT_CAPACITY];}//初始化elem数组public void initElem(int[] array) {/*elem = Arrays.copyOf(array,array.length);usedSize = elem.length;*/for (int i = 0; i < array.length; i++) {elem[i] = array[i];usedSize++;}}//创建大根堆public void createHeap() {//从最后一个棵子树开始调整//这里用usedSize 是因为数组中元素可能没有全部赋值//parent 可以取到0，就是这棵二叉树的根节点for (int parent = (usedSize - 1 - 1) / 2; parent >= 0; parent--) {//找到每颗子树最大值并与根节点交换，向下调整siftDown(parent, usedSize);}}//向下调整private void siftDown(int parent, int len) {int child = 2 * parent + 1;//while 表示向下调整不只一次//child < len 表示至少有左孩子while (child < len) {//判断是否有右孩子防止越界，同时左孩子和右孩子比较大小if (child + 1 < len && elem[child] < elem[child + 1]) {child = child + 1;}//走完上述if语句，证明child 一定保存的是左右两个孩子最大值的下标//判断是否要与当前子树根节点交换if (elem[child] > elem[parent]) {swap(child, parent);//parent中小的元素往下移动，可能会造成子树不满足堆的性质，因此需要继续向下调整parent = child;child = 2 * parent + 1;} else {break;}}}private void swap(int i, int j) {int tmp = elem[i];elem[i] = elem[j];elem[j] = tmp;}
}

siftDown(int parent, int len); 向下调整传入的参数是，子树的根节点以及每颗子树结束的位置。 

• 注意：在调整以parent为根的二叉树时，必须要满足parent的左子树和右子树已经是堆了才可以向下调整。
• 时间复杂度分析：最坏的情况即图示的情况，从根一路比较到叶子，比较的次数为完全二叉树的高度，即时间复杂度为O()

2.4.2 建堆的时间复杂度 O(N)

向下调整的方式，建立大根堆/小跟堆，时间复杂度为O(N)

• 因为堆是完全二叉树，而满二叉树也是完全二叉树，此处为了简化使用满二叉树来证明(时间复杂度本来看的就是近似值，多几个节点不影响最终结果)：
• 最后一层不需要向下调整，我们从倒数第二层往上都是要向下调整，每一层调整的高度不同；例如下图 ，第三层每个节点调整的高度为1层，第二层每个节点调整的高度为2层，第一层每个节点调整的高度为3层；且每层的节点个数不一样。
• 算每一层节点数与每层每个节点需要向下调整的次数想乘，算出每层节点向下调整的次数，然后每一层再相加，就能算出来这棵满二叉树节点向下调整的总次数，就是时间复杂度。

最后要把问题转换为和问题模相关的函数；log2(N+1)随着问题规模的扩大，即N越大，该函数趋于一个稳定的值。

因此：向下调整建堆的时间复杂度为O(N)

2.5 堆的插入与删除

2.5.1 堆的插入（向上调整方式）

堆的插入总共需要两个步骤： 先插入，再向上调整。

1. 先将元素放入到底层空间中（插入到堆的末尾，即最后一个孩子节点之后 ；数组的有效元素之后）(注意：空间不够时需要扩容)
2. 将最后新插入的节点向上调整，直到满足堆的性质。

• 向上调整这种方式，时间复杂度为：树的高度 O()
• 思路：已知插入节点的下标(c)位置，可以通过(c-1) / 2 求得父节点的下标（p），我们只需要将插入后的节点跟父节点比较大小就可了，因为在没有插入节点之前这个堆就是一个大根堆（堆里其他的子树都满足大根堆的性质），根据大小看是否向上调整。
• 终止条件：p < 0 或者是 c = 0 向上调整就调整完了。

//插入,插入到堆末尾
public void push(int val) {//判断数组是否满了，满了扩容if (isFull()) {elem = Arrays.copyOf(elem, 2 * elem.length);}//插入到堆末尾elem[usedSize] = val;//向上调整siftUp(usedSize);usedSize++;
}public boolean isFull() {return usedSize == elem.length;
}//向上调整
private void siftUp(int child) {int parent = (child - 1) / 2;while (child > 0) {if (elem[child] > elem[parent]) {swap(child, parent);child = parent;parent = (child - 1) / 2;} else {break;}}
}

2.5.2 向上调整建堆的时间复杂度

向上调整的方式，建立大根堆/小跟堆，时间复杂度为O(N*log2N)

最后一层也参与向上调整，一般不采用向上调整建堆。 

【小结】

向上调整和向下调整这种方式的时间复杂度都是，树的高度。 h = log2(N)

建堆的方式不止一种；

1. 可以把整体数组元素全部给程序，然后以每颗子树向下调整的方式去建堆。
2. 可以不给数组元素，然后插入，来一个插入一个，通过向上调整的方式去建堆。

向下调整建堆的时间复杂度 O(N) 相对来说比较快一点。

向上调整建堆的时间复杂度为O(N*log2N)

2.5.3 堆的删除

注意：堆的删除一定删除的是堆顶元素。具体如下： 先交换，后删除，再向下调整。

1. 将堆顶元素与堆中最后一个元素交换
2. 将堆中有效数据个数减少一个(usedSize--)
3. 对堆顶元素进行向下调整(调整为堆之前的排序，大根堆)

交换，删除后只有0下标这棵树不是大根堆，其他树都是大根堆，此时只需要调整0下标这棵树就行了（向下调整）。65在这已经删除掉了，不考虑它了。

//删除元素，删除的一定是堆顶元素
public int pop() {if (usedSize == 0) {return -1;//或者抛出自定义异常}int oldVal = elem[0];//堆顶元素与堆中最后一个元素交换swap(0,usedSize-1);//删除usedSize--;//向下调整siftDown(0,usedSize);return oldVal;
}

这里usedSize = 9，已经不包含65了。

16和8 不用再比较了，因为8已经删除了

3. 常用接口介绍

3.1 PriorityQueue的特性

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

 关于PriorityQueue的使用注意事项： PriorityQueue底层默认是小根堆

class Student {public int age;public String name;public Student(int age, String name) {this.age = age;this.name = name;}@Overridepublic String toString() {return "Student{" +"age=" + age +", name='" + name + '\'' +'}';}
}public class Test {public static void main(String[] args) {/*PriorityQueue<Integer> priorityQueue = new PriorityQueue<>();priorityQueue.offer(10);priorityQueue.offer(5);priorityQueue.offer(6);*/PriorityQueue<Student> priorityQueue2 = new PriorityQueue<>();priorityQueue2.offer(new Student(10,"zhangsan"));priorityQueue2.offer(new Student(20,"lisi"));System.out.println("============");}
}

• 类型装换异常，没有实现Comparable接口，不知道两个学生(Student)拿什么比较。
• 查看PriorityQueue类中offer方法源码可知，在元素插入非空堆中需要向上调整(默认小根堆)，而向上调整需要进行比较，查看比较方法要么使用Comparator 要么使用Comparable；但是上述代码没有在创建堆对象时传入比较器Comparator，且Student类没有实现Comparable接口，所以比较不了。
• 因此自定义的堆要比较大小，一定要在创建堆对象时传入比较器Comparator 或者 自定义类实现 Comparable接口， 告诉程序拿什么比较。

内部定义的比较器对象，用来接收用户实例化PriorityQueue对象时提供的比较器对象。

comparator比较器默认为null

创建对象没有提供比较器参数构造方法，插入元素时，则默认实现Comparable接口。

注意如果只插入一个元素且是第一次插入元素时，不会抛出异常，因为第一次插入元素不需要进行比较。查看offer源码：

3、不能插入null对象，否则会抛出NullPointerException。上图源码

判断题：Java的数组容量可以分配无限大。是不对的，最多是堆的大小，一般情况下会规定是整型的最大值（2147483647）

3.2 PriorityQueue常用方法介绍

3.2.1 优先级队列的构造

此处只是列出了PriorityQueue中常见的几种构造方式，其他的可以参考帮助文档。

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

PriorityQueue() 不带参数的构造方法

• 源码调用了带有两个带参数的构造方法，里面的参数是：一个初始容量默认为11，另一个默认没有比较器。
• 如果传入比较器，则使用传入的比较器。

PriorityQueue(int initialCapacity) 带一个参数的构造方法

PriorityQueue(Comparator<? super E> comparator) 带一个参数(比较器)的构造方法 

比较器默认为null

• 源码也是调用了带有两个带参数的构造方法，里面的参数是：一个指定的初始容量，另一个默认没有比较器。
• 且指定的初始容量 不能小于1，否则会抛出异常IllegalArgumentException 可查看上面的代码

带一个比较器参数的构造方法，传入比较器

PriorityQueue(Collection<? extends E> c)  用一个集合来创建优先级队列

先把list中的元素构建成小根堆，然后再offer插入，向上调整

public static void main(String[] args) {List<Integer> list = new LinkedList<>();list.add(1);list.add(6);//小根堆PriorityQueue<Integer> priorityQueue = new PriorityQueue<>(list);priorityQueue.offer(10);priorityQueue.offer(20);System.out.println(priorityQueue.poll());
}
//执行结果
1

3.2.2 PriorityQueue构造大根堆

默认情况下，PriorityQueue队列是小根堆，如果需要大根堆需要提供比较器。

//自己定义的比较器:直接实现Comparator接口，然后重写该接口中的compare方法即可
class Imp implements Comparator<Integer> {@Overridepublic int compare(Integer o1, Integer o2) {//小根堆//return o1.compareTo(o2);//大根堆return o2.compareTo(o1);}
}public class Test {public static void main(String[] args) {Imp imp = new Imp();PriorityQueue<Integer> priorityQueue = new PriorityQueue<>(imp);priorityQueue.offer(10);priorityQueue.offer(5);priorityQueue.offer(6);}
}

【小结】

创建堆对象时，调用不传入比较器构造方法

• 在插入元素向上调整默认调用Comparable比较，且插入的元素是可比较的实现了Comparable接口，否则会抛出ClassCastException异常（类型转换异常）。
• 因为插入元素调用Comparable接口时底层发生了强制类型转换。

创建堆对象时，调用传入比较器构造方法

在插入元素向上调整默认调用传入的比较器Comparator比较。

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

函数名	功能介绍
boolean offer(E e)	插入元素e，插入成功返回true，如果e对象为空，抛出NullPointerException异常，时 间复杂度O(log2N) ，注意：空间不够时候会进行扩容
E peek()	获取优先级最高的元素，如果优先级队列为空，返回null
E poll()	移除优先级最高的元素并返回，如果优先级队列为空，返回null
int size()	获取有效元素的个数
void clear()	清空
boolean isEmpty()	检测优先级队列是否为空，空返回true

public static void main(String[] args) {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("优先级队列不为空");}
}
//执行结果
10
0
8
2
0
优先级队列已经为空!!!

3.2.4 扩容方式（PriorityQueue）

注意：以下是JDK 1.8中，PriorityQueue的扩容方式： 扩容就找grow方法(在offer方法中)。

创建一个空的优先级队列，假设默认空间容量给的是10，这里方便计算理解。实际上给的是11

TOP - K 问题   O(N*logK)

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

• TOP-K问题：即求数据集合中前K个最大的元素或者最小的元素，一般情况下数据量都比较大。例如，一万个数据中，找到前10个最大的。
• 对于Top-K问题，能想到的最简单直接的方式就是排序，但是：如果数据量非常大，排序就不太可取了(数据可能不会一下子全部加载到内存中)，而且速度会很慢。

最小的K个数，使用堆来解决：

第一种方法：整体建立一个小根堆；取10次堆顶元素。O((N+K)*logN)

public int[] smallestK(int[] arr, int k) {int[] ret = new int[k];if (arr == null || k == 0) {return ret;}PriorityQueue<Integer> priorityQueue = new PriorityQueue<>(arr.length);//通过插入建堆，默认小根堆//相当于以向上调整的方式 建立小根堆 O(N*logN)for (int i = 0; i < arr.length; i++) {priorityQueue.offer(arr[i]);}//删除堆顶元素k次 O(K*logN)//每删除一个元素，都要向下调整，只调整0下标为根节点这一颗树for (int i = 0; i < k; i++) {ret[i] = priorityQueue.poll();}return ret;
}

• 这里是将一万个数据（整个数组）创建成了小根堆，然后利用删除堆元素的性质，每删一次都会调整为小根堆，因此删10次就可以得到前10个最小的元素了。
• 这样方法也可以，但是非常的浪费时间（创建这么大的堆，而且每删一个元素都要去向下调整这么大数据量的堆），并不是我们最终解决Top-k问题的方法

• 时间复杂度为O((N+K)*logN)

第二种方法：最佳解决方法 O(N*logK)

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

• 前K个最大的元素，则建小堆(大小是k)

解释：当遍历到数组元素大于堆顶的时候，说明此时堆顶的元素一定不是前K个最大的值。遍历结束后，小根堆中是前K个最大的值，堆顶元素是这K个最大的值里面最小的。

• 前K个最小的元素，则建大堆(大小是k)

解释：当遍历到数组元素小于堆顶的时候，说明此时堆顶的元素一定不是前K个最小的值。遍历结束后，大根堆中是前K个最小的值，堆顶元素是这K个最小的值里面最大的。

2. 用剩余的N-K个元素依次与堆顶元素来比较，不满足则入堆替换堆顶元素

将剩余N-K个元素依次与堆顶元素比完之后，堆中剩余的K个元素就是所求的前K个最小或者最大的元素。

• 因为TOP-K问题一般情况下都是在大量数据里面求最小的K个值，其中K个元素很小，一般可以忽略不计（相对于数据量N来说）
• 所以建堆(向上调整)的时候和调整堆(向下调整)的时候 时间复杂度 (只要涉及K的)可以忽略不计可以忽略。

class Imp implements Comparator<Integer> {@Overridepublic int compare(Integer o1, Integer o2) {//小根堆//return o1.compareTo(o2);//大根堆return o2.compareTo(o1);}
}public class Test {//求前k个最小元素public int[] smallestK(int[] arr, int k) {int[] ret = new int[k];if (arr == null || k <= 0) {return ret;}//创建对象时，传入了比较器PriorityQueue<Integer> priorityQueue = new PriorityQueue<>(new Imp());//1. 建立大小为k的大根堆 O(K*logK)for (int i = 0; i < k; i++) {priorityQueue.offer(arr[i]);}//2. 遍历剩下的N-K个元素与堆顶元素比较，删除，插入//O(N-K)*logKfor (int i = k; i < arr.length; i++) {if (arr[i] < priorityQueue.peek()) {priorityQueue.poll();priorityQueue.offer(arr[i]);}}//下面这个不能算topK的复杂度，这个地方是整理数据//K*logKfor (int i = 0; i < k; i++) {ret[i] = priorityQueue.poll();}return ret;}
}

• 提出问题，找到第K小的元素。 找到了前K个最小的元素后，堆顶就是第K小的元素。
• 上一个方法的时间复杂度为O((N+K)*logN) ，这种方式的时间复杂度为O(N*logK) 。当K很小时，N很大时，相对来说快了很多。

可以直接创建匿名内部类：

堆排序   O(N*logN)

堆排序即利用堆的思想来进行排序，总共分为两个步骤：

1. 建堆；从小到大升序：建大根堆；从大到小降序：建小根堆
2. 利用堆删除思想来进行排序

建堆和堆删除中都用到了向下调整，因此掌握了向下调整，就可以完成堆排序。

从小到大排序示例：

问题分析：为什么不用小根堆，首先小根堆只能保证根比左右孩子小，不能知道左右孩子谁大；如果用每次弹出堆顶的元素放到数组里面，堆变成小根堆，然后再弹出放到数组中进行排序，虽然这样确实有序，但是弹出的元素需放到一个新的数组中，并不是在数组本身上进行操作（要求：对数组本身进行排序）而且重新创建了一个新的数组浪费空间，空间可能还存不下这些元素。

思路：

• 利用大根堆，堆顶元素与未排序的最后一个元素交换，交换完后最大的元素在数组的最后且有序（跟堆的删除是一样的），
• 然后树向下调整为大根堆，堆顶元素再与未排序的最后一个元素交换，这样一定保证了最大的元素放在最后，以此类推 直到全部有序。

建完堆（大根堆）之后，在排序的时候，交换了0下标和最后待排序下标的值，此时只有0下标这棵树不是大根堆，其他的(子)树都是大根堆，所以我们只需要向下调整0下标这棵树为大根堆就可以了，排序的数据有N个，所以排序的时间复杂度O(N*logN)

public void heapSort() {int end = usedSize - 1;while (end > 0) {swap(0,end);siftDown(0,end);end--;}
}

---

好啦Y(^o^)Y，本节内容到此就结束了。下一篇内容一定会火速更新！！！

后续还会持续更新数据结构与算法方面的内容，还请大家多多关注本up，第一时间获取新鲜的知识。

如果觉得文章不错，别忘了一键三连哟！