【数据结构】优先级队列（堆）
| 阿里云国内75折 回扣 微信号：monov8 |
| 阿里云国际，腾讯云国际，低至75折。AWS 93折 免费开户实名账号 代冲值 优惠多多 微信号：monov8 飞机：@monov6 |
成功就是失败到失败也丝毫不减当初的热情
目录
1.理解优先级队列
在前面博文中我们学习了队列那我们现在也知道了队列是遵循先进先出原则的一种数据结构。 那接下来我们就一起来学习优先级队列。
优先级队列PriorityQueue顾名思义我们应该就可以想到肯定是队列里面带有优先级优先级高的数据优先出队。比如我们平时玩手机的时候要是有人给你打个电话页面就会直接跳转到接电话的那个页面那么也就说明手机来电话的优先级要比手机其他操作的优先级要高。
2.优先级队列的底层
在 jdk1.8 版本中优先级队列的底层其实就是一个堆。
2.1 认识堆
2.1.1 堆的概念
堆的概念堆具有结构性也就是它是采用数组表示的完全二叉树。堆还具有有序性也就是根节点大于子节点或者小于子节点。
通过根节点大于子节点或小于子节点又可以将堆分为大顶堆和小顶堆
大顶堆又称为最大堆也就是树中所有父节点都要大于或等于子节点
小顶堆又称为最小堆也就是树中所有父节点都要小于或等于子节点
2.2.2 堆的存储
堆的存储数据都是存储在数组中完全二叉树是我们想象出来的
我们可以通过数组对应的下标找出二叉树的父子关系
| 左节点leftChild | leftChild = parent * 2 + 1 |
| 右节点rightChild | rightchild = parent * 2 + 1 + 1 = leftchild + 1 |
| 父节点parent | parent =child - 1/ 2 |
2.2 堆的创建
2.2.1 向下调整算法
向下调整算法前提用向下调整算法有一个前提就是左右子树必须都是堆要是建大顶堆左右子树必须都是大顶堆要是建小顶堆左右子树必须都是小顶堆。
例建小顶堆使用向下调整算法首先左右子树都必须是小顶堆
第一步先判断左右子树是否都为小顶堆要是为小顶堆就可以进行第二步向下调整算法
第二步向下调整算法找出根结点的左子树和右子树小的那个然后与根结点比较如果小于根结点就交换如果不小于则这整颗数都是小堆不需要交换。依次循环直到找到叶子结点终止
例现在有一个数组里面的元素为{27,15,19,18,26,37}现在需要将它进行向下调整成为小顶堆
首先我们将它想成一棵完全二叉树
通过图片我们可以发现根节点的左右子树都是小根堆那么接下来我们可以直接使用向下调整算法使完全二叉树变为小根堆。首先将数组和需要调整节点的下标传给 shiftDown 方法的形参数组 array 和整型 parent 然后我们可以通过 parent 找到左子节点将左子节点下标存放在 child 变量中。然后判断存放在 child 变量中的左子节点是否存在如果存在我们就进入循环。然后判断右子节点是否存在如果存在则判断右子节点是否比左子节点小要是小就让child存放右子节点的下标。然后在判断 parent 下标对应的值是否小于 child 下标对应的值如果小于就交换然后一值循环直到不小于或者child下标不存在时跳出循环此时便是小根堆了
//向下调整,建小顶堆arr是存放数据的数组size是有效元素的个数
public void shiftDown(int[] arr, int parent) {
int child = parent * 2 + 1;
while (child < size) {
if (child + 1 < size && arr[child + 1] < arr[child]) {
child += 1;
}
if (arr[parent] <= arr[child] ) {
break;
} else {
int tmp = arr[parent];
arr[parent] = arr[child];
arr[child] = tmp;
parent = child;//交换之后需要接着向下调整
child = parent * 2 + 1;
}
}
}2.2.2 堆的创建
上面讲解了向下调整算法如果建大顶堆那么左右子树必须都是大顶堆如果建小顶堆那么左右子树必须都是小顶堆这种情况下才能用向下调整算法。
那么对普通的序列根节点的左右子树不满足堆的特性又该如何调整呢
例 现在有一个数组里面的元素为 {1,5,3,8,7,6}现在需要将其成为大顶堆
首先我们需要找到最后一个非叶子节点 那么它的左右子树肯定是叶子节点叶子节点没有子节点那么它们就是堆那我们就可以调用向下调整算法那么此时最后一棵非叶子节点也就变成了堆然后我们就依次将每个非叶子节点都通过向下调整算法变成堆那么此时通过向下调整的非叶子节点也都变成了堆一直调整到根节点即可变成堆
//建堆arr是存放数据的数组size是有效元素的个数
public void buildHeap(int[] arr) {
if (arr == null) {
return;
}
int lastNoLeafNode = (size - 1 - 1) / 2;
while (lastNoLeafNode >= 0) {
shiftDown(arr,lastNoLeafNode);
lastNoLeafNode--;
}
}
//向下调整,建大顶堆
public void shiftDown(int[] arr, int parent) {
int child = parent * 2 + 1;
while (child < size) {
if (child + 1 < size && arr[child + 1] > arr[child]) {
child += 1;
}
if (arr[parent] >= arr[child] ) {
break;
} else {
int tmp = arr[parent];
arr[parent] = arr[child];
arr[child] = tmp;
parent = child;
child = parent * 2 + 1;
}
}
}2.3 堆的插入
堆的插入操作也就是将元素插入到堆中的操作插入后依然满足堆的性质
堆的插入的步骤
- 第一步 先将元素插入到数组最后一个元素的后面(注插入前需要判断是否需要扩容)
- 第二步将插入的元素依次向上调整直到满足堆的性质
例如我们现在有一个数组数组中的元素为{1,5,3,8,7,6}
从这个数组和想象出来的完全二叉树我们也就可以看出它是小顶堆那么现在我们需要插入一个元素 2应该怎么做呢
第一步判断是否需要扩容然后将 2 插入到数组最后一个元素的后面
第二步将插入的元素依次向上调整直到满足堆的性质
注既然在未插入之前它本来就是个小堆那么插入得时候只需向上调整即可
//插入arr 是存储数据的数组size 是有效元素个数
public void insert(int num) {
if (size >= arr.length) {
grow();
}
arr[size++] = num;
int last = size - 1;
shiftUp(last);
}
//扩容
private void grow() {
arr = Arrays.copyOf(arr,arr.length * 2);
}
//向上调整
public void shiftUp(int child) {
int parent = (child - 1) / 2;
while (child > 0) {
//因为本来就是一个小根堆所以只需将插入得值与父节点的值比较
if (arr[child] < arr[parent]) {
int tmp = arr[child];
arr[child] = arr[parent];
arr[parent] = tmp;
child = parent;
parent = parent = (child - 1) / 2;
} else {
break;
}
}
}2.4 堆的删除
堆的删除一定删除的是堆顶元素
堆的删除步骤
- 第一步将堆中最后一个元素赋值给堆顶元素
- 第二步将堆中的有效元素减一
- 第三步将堆顶元素向下调整
例如我们现在有一个数组数组中的元素为{1,5,3,8,7,6}
我上面的数组以及图我们可以发现这是一个小顶堆那么我们现在需要删除它的堆顶元素删除之后它依然是一个小顶堆应该怎么做呢
第一步将最后一个元素赋值给堆顶元素有效元素个数减一就相当于数组中删除了一个元素
第二步将堆顶元素进行向下调整
//删除arr 是存储数据的数组size 是有效元素个数
public int poll() {
int tmp = arr[0];
arr[0] = arr[--size];
shiftDown(arr,0);
return tmp;
}
//向下调整,建小顶堆
public void shiftDown(int[] arr, int parent) {
int child = parent * 2 + 1;
while (child < size) {
if (child + 1 < size && arr[child + 1] < arr[child]) {
child += 1;
}
if (arr[parent] <= arr[child] ) {
break;
} else {
int tmp = arr[parent];
arr[parent] = arr[child];
arr[child] = tmp;
parent = child;//交换之后需要接着向下调整
child = parent * 2 + 1;
}
}
}2.5 查看堆顶元素
直接返回堆顶值即可
//查看堆顶元素
public int pook() {
return arr[0];
}关于堆操作的代码阿紫姐姐写的并不是很完善大家可以自行完善一下比如每次对堆进行删除和插入之前都进行判空一下等等。
2.6 堆的运用
优先级队列的底层其实也就是堆那我们学习了堆其实也就相当于学习了优先级队列
堆可以用来进行排序
- 升序建大堆
- 降序建小堆
后面的排序博文中会讲堆排序 大家目前先不用管堆排序
3.PriorityQueue
3.1 PriorityQueue 的特性
在Java集合框架中其实提供了两种类型的优先级队列分别是 PriorityQueue 和 PriorityBlockingQueue
- PriorityQueue线程不安全
- PriorityBlockingQueue是线程安全的
那我们本次主要讲解 PriorityQueue
当我们在使用 Java 自带的集合 PriorityQueue 时需要注意
- 使用 PriorityQueue 时导入PriorityQueue 所在的包
- PriorityQueue 中放置的元素必须要能够比较大小不能插入无法比较大小的对象否则会抛出 ClassCastException 异常
- PriorityQueue 中不能插入null对象否则会抛出 NullPointerException
- PriorityQueue 底层使用了堆数据结构
- PriorityQueue 默认情况下是小堆
默认情况下PriorityQueue队列是小堆如果需要大堆需要用户提供比较器
用户自己定义的比较器直接实现Comparator接口然后重写该接口中的compare方法即可
import java.util.Comparator;
class IntCmp implements Comparator<Integer>{
@Override
public int compare(Integer o1, Integer o2) {
return o2-o1;
}
}3.2 PriorityQueue 的构造方法
目前我们只介绍 PriorityQueue 常用的几种构造方法
3.2.1 无参构造方法
创建一个空的优先级队列默认容量是 11
3.2.2 指定容量构造方法
创建一个初始容量为 initialCapacity 的优先级队列
注意 initialCapacity 不能小于1否则会抛 IllegalArgumentException 异 常
3.2.3 用一个集合来创建优先级队列
用一个集合来创建优先级队列
3.3 PriorityQueue 常用的成员方法
| 方法名 | 功能介绍 |
| boolean offer(E e) | 插入元素插入成功返回 true 否则返回 false。如果 e 对象为空抛出 NullPointerException 异常。空间不够会扩容 |
| E peek() | 查看堆顶元素并返回如果优先级队列为空则返回null |
| E poll() | 删除堆顶元素并返回如果优先级队列为空则返回null |
| int size() | 获取优先级队列有效元素的个数 |
| void clear() | 清空优先级队列里面的元素 |
| boolean isEmpty() | 判断优先级是否为空为空返回true否则返回false |
在JDK 1.8中PriorityQueue的扩容方式
如果容量小于64时是按照oldCapacity的2倍方式扩容的
如果容量大于等于64是按照oldCapacity的1.5倍方式扩容的
如果容量超过MAX_ARRAY_SIZE按照MAX_ARRAY_SIZE来进行扩容
3.4 优先级队列的运用
优先级队列经常用来解决 top-k 的问题。比如班级前三的同学
接下来我们就用 top-k 完成一道面试题
面试题最小 k 个数题目来源力扣
题目描述设计一个算法找出数组中最小的k个数。以任意顺序返回这k个数均可。
输入 arr = [1,3,5,7,2,4,6,8], k = 4
输出 [1,2,3,4]
思路题目需要返回数组中的最小的 k 个数那么我们就可以把数组的前 k 个数构成一个大堆然后从第 k 个下标开始依次跟堆顶比较如果小于堆顶就删除堆顶的元素然后插入第 k 下标对应的元素整个数组都与堆顶比较完后那么堆里面剩下的就是数组中最小的 k 个数了
import java.util.Comparator;
import java.util.PriorityQueue;
public class Test {
public static void main(String[] args) {
int[] arr = {1,3,5,7,2,4,6,8};
int k = 4;
int[] arrTmp = smallestK(arr,k);
for (int i = 0; i < arrTmp.length; i++) {
System.out.print(arrTmp[i]+" ");
}
}
public static int[] smallestK(int[] arr, int k) {
int[] retArr = new int[k];
for (int i = 0; i < retArr.length; i++) {
retArr[i] = arr[i];
}
PriorityQueue<Integer> priorityQueue = new PriorityQueue<>(new IntCmp());
for (int i = 0; i < k; i++) {
priorityQueue.offer(retArr[i]);
}
int t = k;
while (t < arr.length) {
if(priorityQueue.isEmpty()) {
break;
}
int tmp = priorityQueue.peek();
if (arr[t] < tmp) {
priorityQueue.poll();
priorityQueue.offer(arr[t]);
}
t++;
}
for (int i = 0; i < k; i++) {
if (priorityQueue.isEmpty()) {
break;
}
retArr[i] = priorityQueue.poll();
}
return retArr;
}
}
class IntCmp implements Comparator<Integer> {
@Override
public int compare(Integer o1, Integer o2) {
return o2 - o1;
}
}