文章目录
优先级队列 - 堆 - PriorityQueue
前言 ： 恭喜你已经将二叉树学完了，二叉树算目前来止学习的比较难的数据结构，本文介绍的优先级队列就比较简单，下面就来学习一下。
1. 什么是优先级
优先级，可以讲我们都遇到过，在初高中时，我们的座位可能是按照成绩来安排的，比如成绩好的可以先来挑选座位， 而成绩一般的同学最后只能挑选到比较靠后的位置这里就是一种优先级，成绩高的同学优先。
再来一个例子 ： 手机打游戏
现在我们的手机打游戏 ，在手机来的时候，那个来电信息会出现在最上面我们是可以变打电话边打游戏的， 按照之前的手机 ，如果来了电话就会直接弹出通话页面， 这里也是一种优先级 ，电话 > 大于 游戏 .
到此我们就知道了优先级 ， 下面继续。
看到标题是优先级队列 - 堆 - PriorityQueue
有没有 疑问，为啥这里我们讲 优先级队列后面会跟一个 堆 ？
其实 在我们 JDK 1.8 中 我们 优先级队列 PriorityQueue 底层 是使用堆的数据结构 。
那么 什么是 堆呢 ？ 下面就来学习一下
补充 ： 优先级队列实现了 Queue 这个接口 ， 是可以使用 队列的方法的
2. 堆
堆其实就是在完全二叉树的基础之上进行了一些元素的调整。
2.1 堆的概念与存储
如果有一个关键码的集合K = {k0，k1， k2，…，kn-1}，把它的所有元素按完全二叉树的顺序存储方式存储 在一个一维数组中，并满足：Ki <= K2i+1 且 Ki<= K2i+2 (Ki >= K2i+1 且 Ki >= K2i+2) i = 0，1，2…，则称为 小堆(或大堆)。将根节点最大的堆叫做最大堆或大根堆，根节点最小的堆叫做最小堆或小根堆。
概念认识一下就ok，下面直接来看图
知道了 大根堆 和 小根堆 ，那么我们的 堆 是如何存储的呢？
之前我们说 堆 是再完全二叉树的基础上对一些元素进行调整而来， 此时肯定会认为 堆是跟二叉树那样存储的， 其实我们的堆在逻辑上是一颗完全二叉树 ，而本质上(物理上) 是通过 数组 存储的 。
补充 ： 数组存储树时，一般存储完全二叉树
这里我们知道了堆是通过数组来存储的，通过层序遍历讲元素放入数组当中，这里给两棵树一颗完全二叉树，一颗二叉树来对比一下。
这里我们 堆的 概念 和 堆的存储 就学完了，下面我们就来创建我们的堆 。
2.2 堆的创建
1. 复习二叉树性质 ：
这里我们 想要 完成堆的创建，这里就需要复习一下二叉树的性质 ， 这里就来稍微看一看 。
如果i为0，则i表示的节点为根节点，否则i节点的双亲节点为 (i - 1)/2
如果2 * i + 1 小于节点个数，则节点i的左孩子下标为2 * i + 1，否则没有左孩子
如果2 * i + 2 小于节点个数，则节点i的右孩子下标为2 * i + 2，否则没有右孩子
2. 给定一个数组， 通过数组里的结果集合创建大根堆
这里我们就通过我们这个数组还原的完全二叉树来一步一步的创建大根堆 。
注意 ：下面的 prent 敲错了，是 parent ，我的锅
3. 通过 (child - 1) / 2 拿到我们的 父亲节点 ， 通过 elem[prent] 与 elem[child] 比较，当父亲节点小于孩子节点交换
注： elem 就是我们的数组， prent 和 child 都是下标
此时我们 就成功的调整了 一对父和子 ， 那么我们要如何去调整下一对呢？
非常简单，我们直接让 prent --即可， 这样就 到 18这个节点处 。
4. prent – 得到下一个父亲节点
此时 3 下标的父亲节点也就调整完了，下面继续让 prent –
2 下标的父节点也交换完了，继续让 prent –
那么 有疑问了， 此时我们的 prent 等于了3 下标，我们还能再 减减吗？
此时只能说看官别急，这里我们prent 是通过传参给的,后面会重新更新prent的参数信息所以没有关系，如果这里看不懂，等下看代码就会恍然大悟的。
继续 prent –
代码实现 :
图一：
代码 ：
/**
* 向下调整
*/
public void shifDown(int parent, int len) {
// parent --> 父亲节点当参数传过来 ， len == elem.length
// 1. 通过 2 * parent + 1 求出左孩子节点
int child = 2 * parent + 1;
while (child < len) {
if (child + 1 < len && elem[child] < elem[child + 1]) {
child++;
}
// 判断当前 child 于 parent 对应的值大小
if (elem[child] > elem[parent]) {
int tmp = elem[child];
elem[child] = elem[parent];
elem[parent] = tmp;
// 更新 parent 于 child ，
parent = child;
child = 2 * parent + 1;
} else {
// 这里我们已经是大根堆了
// 那么就没必要继续下去判断了。
break;
}
}
}
public void initElem(int[] array) {
// array 给的 数组
for (int i = 0; i < array.length; i++) {
elem[i] = array[i];
usedSize++;
}
}
public void createHeap() {
// 1. usedSize == elem.length
// 2. usedSize - 1 == child 最后一个孩子节点
// 3. parent = (child - 1) / 2 二叉树性质
for (int parent = (usedSize - 1 - 1) / 2; parent >= 0; parent--) {
shifDown(parent,usedSize);
}
}
大根堆知道了咋创建，那么小根堆不也是一样的吗就是再我们的向下调整的代码上改一下即可
/**
* 向下调整 小根堆
*/
public void shifDown2(int parent, int len) {
int child = 2 * parent + 1;
while (child < len) {
if (child + 1 > len && elem[child] > elem[child + 1]) {
child++;
}
//判断 parent 于 child 位置的大小
if (elem[child] < elem[parent]) {
int tmp = elem[parent];
elem[parent] = elem[child];
elem[child] = tmp;
// 改变 parent
parent = child;
child = 2 * parent + 1;
} else {
break;
}
}
}
public void initElem(int[] array) {
// array 给的 数组
for (int i = 0; i < array.length; i++) {
elem[i] = array[i];
usedSize++;
}
}
public void createHeap() {
// 1. usedSize == elem.length
// 2. usedSize - 1 == child 最后一个孩子节点
// 3. parent = (child - 1) / 2 二叉树性质
for (int parent = (usedSize - 1 - 1) / 2; parent >= 0; parent--) {
shifDown(parent, usedSize);
}
}
提问 ： 向下调整是创建堆的精髓，那么再这里提问，我们的向下调整的时间复杂度是多少呢？
那么再来 我们建堆的时间复杂度是多少呢？
因为堆是完全二叉树，而满二叉树也是完全二叉树，此处为了简化使用满二叉树来证明(时间复杂度本来看的就是近似值，多几个节点不影响最终结果)：
n = 2 ^ h - 1 和 h = log2(n + 1) 是我们二叉树的性质 不懂可以回到二叉树看一看性质 , 一个通过高度求节点数， 一个通过节点数求高度.
所以我们的建堆的时间复杂度为 O(N)
此时我们 堆创建完了， 时间复杂度也讲完了，那么下面我们来 写两个常规的操作 ， 入堆和出堆操作 。
2.3 堆的插入 offer
这里我们堆插入是需要使用向上调整的 这里 通过 图来了解一下我们的 插入操作
可以看到我们每次插入一个元素 是不是放在了数组的最后面 然后通过向上调整，调整为新的大根堆，如果数组满了那么我们扩容即可
代码实现:
//交换
public void swap(int[] arr, int i, int j) {
int tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
}
private void shiftUp(int child) {
// 1. 通过孩子节点找到父亲
int parent = (child - 1) / 2;
// 2.向上调整
while (child != 0) {
if (elem[child] > elem[parent]) {
swap(elem, child, parent);
//更新父亲和孩子
child = parent;
parent = (child - 1) / 2;
} else {
//此时说明已经不需要调整了
break;
}
}
}
public void offer(int val) {
//1. 判断是否需要扩容
if (isFull()) {
// 扩容
elem = Arrays.copyOf(elem, 2 * elem.length);
}
elem[usedSize++] = val;
// 向上调整 --> 传入最后节点的下标
shiftUp(usedSize - 1);
}
// 判断数组是否满了
public boolean isFull() {
return elem.length == usedSize;
}
调试看看我们的入堆操作 ，可以发现我们的的新增操作就完美完成了 （新增后完成了大根堆的调整）
这里还有一个问题 我们的向下调整是可以完成建堆操作的，那么我们的向上调整能不能呢？
答案 ： 向上调整是可以创建我们的堆的， 这里我们只需要一个一个的插入即可 。
新增操作完成了，下面来实现的删除操作
2.4 堆的删除 poll
堆的删除我们只需要交换 0下标的元素和最后一个下标的元素，然后 向下调整 0 下标即可。
图示：
代码实现 ：
public void shifDown(int parent, int len) {
// parent --> 父亲节点当参数传过来 ， len == elem.length
// 1. 通过 2 * parent + 1 求出左孩子节点
int child = 2 * parent + 1;
while (child < len) {
if (child + 1 < len && elem[child] < elem[child + 1]) {
child++;
}
// 判断当前 child 于 parent 对应的值大小
if (elem[child] > elem[parent]) {
int tmp = elem[child];
elem[child] = elem[parent];
elem[parent] = tmp;
// 更新 parent 于 child ，
parent = child;
child = 2 * parent + 1;
} else {
//此时父亲节大就不需要调整直接返回即可
break;
}
}
}
public int poll(){
// 1.先判断优先级队列是否为空
if(isEmpty()){
throw new RuntimeException("优先级队列为空 !!!"); // 偷懒这里自定义异常
}
int tmp = elem[0];
swap(elem,0,usedSize-1);
//交换换让 usedSize-- ,相当于出元素
// 向下调整
// 此时 userSize 才是最新的最后一个元素
shifDown(0,usedSize-1);
return tmp;
}
// 判断数组是否为空
public boolean isEmpty(){
return usedSize == 0;
}
public void swap(int[] arr, int i, int j) {
int tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
}
到此我们的增加删除操作就完成了， 那我们自己的堆也就差不多实现了，这里补充一个查看堆顶元素的方法
public int peek(){
if(isEmpty()){
throw new RuntimeException("优先队列为空 ！！！");
}
return elem[0];
}
最后整体代码如下：
package Test_10_19.Main;
import java.util.Arrays;
public class TestHeap {
public int[] elem;
public int usedSize;
public TestHeap() {
this.elem = new int[10];
}
/**
* 向下调整
*/
public void shifDown(int parent, int len) {
// parent --> 父亲节点当参数传过来 ， len == elem.length
// 1. 通过 2 * parent + 1 求出左孩子节点
int child = 2 * parent + 1;
while (child < len) {
if (child + 1 < len && elem[child] < elem[child + 1]) {
child++;
}
// 判断当前 child 于 parent 对应的值大小
if (elem[child] > elem[parent]) {
int tmp = elem[child];
elem[child] = elem[parent];
elem[parent] = tmp;
// 更新 parent 于 child ，
parent = child;
child = 2 * parent + 1;
} else {
//此时父亲节大就不需要调整直接返回即可
break;
}
}
}
/**
* 向下调整 小根堆
*/
public void shifDown2(int parent, int len) {
int child = 2 * parent + 1;
while (child < len) {
if (child + 1 > len && elem[child] > elem[child + 1]) {
child++;
}
//判断 parent 于 child 位置的大小
if (elem[child] < elem[parent]) {
int tmp = elem[parent];
elem[parent] = elem[child];
elem[child] = tmp;
// 改变 parent
parent = child;
child = 2 * parent + 1;
} else {
break;
}
}
}
public void initElem(int[] array) {
// array 给的 数组
for (int i = 0; i < array.length; i++) {
elem[i] = array[i];
usedSize++;
}
}
public void createHeap() {
// 1. usedSize == elem.length
// 2. usedSize - 1 == child 最后一个孩子节点
// 3. parent = (child - 1) / 2 二叉树性质
for (int parent = (usedSize - 1 - 1) / 2; parent >= 0; parent--) {
shifDown(parent, usedSize);
}
}
public void swap(int[] arr, int i, int j) {
int tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
}
private void shiftUp(int child) {
// 1. 通过孩子节点找到父亲
int parent = (child - 1) / 2;
// 2.向上调整
while (child != 0) {
if (elem[child] > elem[parent]) {
swap(elem, child, parent);
//更新父亲和孩子
child = parent;
parent = (child - 1) / 2;
} else {
//此时说明已经不需要调整了
break;
}
}
}
public void offer(int val) {
//1. 判断是否需要扩容
if (isFull()) {
// 扩容
elem = Arrays.copyOf(elem, 2 * elem.length);
}
elem[usedSize++] = val;
// 向上调整 --> 传入最后节点的下标
shiftUp(usedSize - 1);
}
// 判断数组是否满了
public boolean isFull() {
return elem.length == usedSize;
}
public int poll(){
// 1.先判断优先级队列是否为空
if(isEmpty()){
throw new RuntimeException("优先级队列为空 !!!"); // 偷懒这里自定义异常
}
int tmp = elem[0];
swap(elem,0,usedSize-1);
//交换换让 usedSize-- ,相当于出元素
// 向下调整
// 此时 userSize 才是最新的最后一个元素
shifDown(0,usedSize-1);
return tmp;
}
// 判断数组是否为空
public boolean isEmpty(){
return usedSize == 0;
}
public int peek(){
if(isEmpty()){
throw new RuntimeException("优先队列为空 ！！！");
}
return elem[0];
}
}
下面我们先来看几道例题，然后就来学习一下 Java库里面的优先级队列 。
3. 例题
1.下列关键字序列为堆的是:()
A: 100,60,70,50,32,65
B: 60,70,65,50,32,100
C: 65,100,70,32,50,60
D: 70,65,100,32,50,60
E: 32,50,100,70,65,60
F: 50,100,70,65,60,32
这道题目非常简单 我们的堆 要不是小根堆， 要不是大根堆，此时我们只需要层序遍历的将每个图画出来或再脑子里过一遍，几乎是可以得到答案的
这里答案就是A
2.已知小根堆为8,15,10,21,34,16,12，删除关键字8之后需重建堆，在此过程中，关键字之间的比较次数是()
A: 1 B: 2 C: 3 D: 4
所以我们的答案是 3次
3.最小堆[0,3,2,5,7,4,6,8],在删除堆顶元素0之后，其结果是()
A: [3，2，5，7，4，6，8]
B: [2，3，5，7，4，6，8]
C: [2，3，4，5，7，8，6]
D: [2，3，4，5，6，7，8]
这道题也非常简单， 画个草图直接一套给他带走，那么答案就是 C
下面就来正式的学习一下我们的优先级队列
4. PriorityQueue
4.1 优先级队列常用的方法
| 函数名 | 功能介绍 |
|---|---|
| boolean offer(E e) | 插入元素e，插入成功返回true，如果e对象为空，抛出NullPointerException异常， 时间复杂度 O(log2 ^ N) ，注意：空间不够时候会进行扩容 |
| E peek() | 获取优先级最高的元素，如果优先级队列为空，返回null |
| E poll() | 移除优先级最高的元素并返回，如果优先级队列为空，返回null |
| int size() | 获取有效元素的个数 |
| void clear() | 清空 |
| boolean isEmpty() | 检测优先级队列是否为空，空返回true |
4.2 PriorityQueue的特性
使用时必须导入PriorityQueue所在的包，即：
import java.util.PriorityQueue;
2. PriorityQueue中放置的元素必须要能够比较大小，不能插入无法比较大小的对象，否则会抛出ClassCastException异常
3. 不能插入null对象，否则会抛出NullPointerException
4. 没有容量限制，可以插入任意多个元素，其内部可以自动扩容
5. 插入和删除元素的时间复杂度为
6. PriorityQueue底层使用了堆数据结构, (注意：此处大家可以不用管什么是堆，后文中有介绍)
7. PriorityQueue默认情况下是小堆—即每次获取到的元素都是最小的元素
补充：Java集合框架中提供了PriorityQueue和PriorityBlockingQueue两种类型的优先级队列，PriorityQueue是线程不安全的，PriorityBlockingQueue是线程安全的，本文主要介绍PriorityQueue。
证明 PriorityQueue 底层默认是 小根堆 ：
4.3 优先级队列源码分析
通过 PriorityQueue中放置的元素必须要能够比较大小，不能插入无法比较大小的对象，否则会抛出ClassCastException异常 引出下面问题
可以看到我们的确是通过 给定的方法完成了我们的比较， 那么他底层是如何调用的呢？
1. 进入PriorityQueue不带参数的构造方法
可以看到他通过 this 调用了调用两个方法的构造方法，此时我们点击DEFAULT_INITIAL_CAPACITY ,
发现他赋值了11， 这里有道翻译一下能供知道他是默认的初始容量
下面继续，我们点击 this 看他带有两个参数的构造方法
此时 init ialCapacity 是不是就是一开始传入的默认容量 11， 而 comparaor 不就是我们的比较器吗 ，传入的参数是null ， 说明没有传入任何东西。
观察发现这里出现了 this.queue 这里我们不知道是啥不要紧 ， CTRL + 鼠标左键 点击它 , 可以看到 他是一个 Object的数组 ，此时我们给他赋值了一个11
最后看我们的 this.comparator = comparator 是不是就是 给我们的比较器赋值只不过我们传入的是null , 所以 此时只是对queue数组进行了实例化。
offer 方法分析
可以看到我们 这样就完成了交换了，如果 我们先存放 了 年龄为 5的学生， 然后再存放年龄为 10的学生，此时我们 key.compareTo((E) e >= 0) 就满足了 10 - 5 >=0 ，所以就会直接退出循环， 然后将 k 下标改为我们传入的 x。
既然我们默认是小根堆，那么我们能不能让他成为大根堆呢？
其实非常简单， 还记得我们给的比较规则吗？
是不是 this.age - o.age 那么我们改成 o.age - this.age 不就成为了我们的大根堆了 吗。
此时我们自定义类型就可以通过PriorityQueue 变成大根堆或小根堆 （取决于我们给定的比较规则） ， 但是有没有想过如果我们是Integer 等其他包装类型呢？他们是由java官方提供的， 我们并没有权力去更改他们的源码 ，那么我们怎么能让它们由默认的小根堆变为大根堆呢？
其实很简单还记得常用的三个接口那篇文章吗，我们就可以传入一个比较器给PriorityQueue 此时不就会根据比较器的规则来比较吗？
三种 常用接口入口
另外我们点击PriorityQueue 也能证明， 来看下面这个带有两个参数的构造方法是不是就有一个比较器的参数。
我们自定义一个 比较器IntCmp , 给定了比较规则，传给了 PriorityQueue 就能实现大根堆
接下来我们来看一下源码
1. 点击 构造方法
2. 点击this 进入带有两个参数的构造方法
3. 点击 offer方法
因为只是 compareTo 与 compare 不同，传入了比较器就会按照我们自己给定的比较规则来比较，所以这里就与之前没有传的过程是一样的只不过比较规则不同就不再继续 咋存的咋比较的了这里自己了解或看之前没传比较器的图。
下面我们就可以总结一下
总结
1.当没有传入数组容量的时候，默认是11
2.当没有传入比较器的时候，它必须是可以比较的
3.优先使用的是比较器来比较
补充 ： 做题可能看到的几种传比较器形式
1.匿名内部类
Lambda 表达式
这里匿名内部类在类和对象那一张讲过了，Lambda会在后面补充 （反射枚举Lambda那边）。
下面我们在来看一下我们的 PriorityQueue 是如何扩容的
最后 queue = Arrays.copyOf(queue, newCapacity); 就完成了我们的扩容操作 。
下面我们来看一下优先级队列的应用Topk问题。
5. Topk问题
在了解Topk问题前 ，先来看一道例题 面试题 17.14. 最小K个数
此时我们肯定会有 第一种想法就是排序，然后通过 找前3个最小的即可
是不是非常简单， 但是假如我们的数据非常多呢 ？ 几十个 G， 那么这样是不是就会有问题 ， 排序是放在我们的内存上进行的，按照我们普遍的玩家的内存情况差不多是 16G 左右， 那么排序是不是就不能完成了。
那么排序不行，那么我们就可以使用我们的堆
这里我们使用堆的时间复杂度是 O(N + KlogN) 那么我们还有没有办法将这个时间复杂度在降低一点呢？
这里就是一个topk为题，下面就来看一下如何解决
这里我们需要找到 前 k个最小的元素，那么就需要创建一个大根堆即可。
代码实现 ：
class Solution {
public int[] smallestK(int[] arr, int k) {
if(k == 0){
return new int[k];
}
// 1. 创建一个大根堆
PriorityQueue<Integer> priorityQueue = new PriorityQueue<>(k, new Comparator<Integer>() {
@Override
public int compare(Integer o1, Integer o2) {
// 大根堆比较规则
return o2.compareTo(o1);
}
});
// 遍历数组中的元素 前 k放进数组中
for(int i = 0;i<arr.length;i++){
if(i < k){
priorityQueue.offer(arr[i]);
}else {
// 此时 优先级对立已经有 k个元素，找到 比堆顶小的元素替换即可
int tmp = priorityQueue.peek();
if(tmp > arr[i]){
// 1. 先弹出
priorityQueue.poll();
// 2. 添加元素
priorityQueue.offer(arr[i]);
}
}
}
// 最后返回数组
int[] arr2 = new int[k];
for(int i = 0;i<k;i++){
arr2[i] = priorityQueue.poll();
}
return arr2;
}
}
这里我们求 k个最小的就已经完成了，那么我想要第 k个小的元素呢？
此时 topk 了解完， 下面来看一下堆排序 。
6. 堆排序
代码实现 ：
public void swap(int[] arr, int left, int right) {
int tmp = arr[left];
arr[left] = arr[right];
arr[right] = tmp;
}
// 向下调整
public void shifDown(int parent, int len) {
int child = 2 * parent; // 通过父亲求孩子
while (child < len) {
if (child + 1 < len && elem[child] < elem[child + 1]) {
child++;
}
if (elem[parent] < elem[child]) {
swap(elem, child, parent);
parent = child;
child = 2 * parent + 1;
}else {
break;
}
}
}
// 堆排
public void heapSort(){
int end = usedSize - 1;
while(end > 0){
swap(elem,0,end);
shifDown(0,end);
end--;
}
}
这里堆排的时间复杂度是多少呢？
第一建堆 时间复杂度O(N) , 然后 end 从 usedSize 走到 0 有 n次，里面还有向下调整，那么时间复杂度就是 O(NlogN) ，
两个相加 O(N) + O(NlogN) ，因为 O(NlogN) 幅度比较大一直在变化， 所以 O(N) 可以省略最总时间复杂度为O(NlogN)
空间复杂度就是O(1) ，没有使用而外的空间。
最后我们来看一道选择题结束本文学习
一组记录排序码为(5 11 7 2 3 17),则利用堆排序方法建立的初始堆为()
A: (11 5 7 2 3 17) B: (11 5 7 2 17 3) C: (17 11 7 2 3 5)
D: (17 11 7 5 3 2) E: (17 7 11 3 5 2) F: (17 7 11 3 2 5)
本文完 。