本文主要是介绍【数据结构】优先级队列 — 堆,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
文章目录
- 前言
- 1. 优先级队列
- 1.1 概念
- 1.2 特性
- 2. 堆
- 2.1 概念
- 2.2 存储方式
- 3. 堆的模拟实现
- 3.1 堆的创建
- 3.2 堆的插入
- 3.3 堆的删除
- 4. PriorityQueue
- 4.1 注意事项
- 4.2 构造器介绍
- 4.3 常用方法介绍
- 5. 经典题型
- 6. 结语
前言
我们之前学习过队列,它是遵循先进先出原则的数据结构,对应我们现实生活中的先到先得原则,比如排队时我们就可以使用队列的数据结构来模拟实现。但是,如果我们想优先操作队列中的某些数据,即让优先级高的元素先出队列,那么这种“普通的”先进先出队列就无法满足我们的需求。这时候就需要“优先级队列”来帮忙了
1. 优先级队列
1.1 概念
优先级队列(Priority Queue)是一种抽象数据类型,它类似于常规的队列或栈,但每个元素都有一个优先级。在优先级队列中,最小元素(或最大元素,根据实现)总是在队列的前端,并且最先被移除。它通常用于需要根据元素的重要性或紧急性进行排序的场景。比如:任务调度,网络数据传输,订单处理等等
1.2 特性
PriorityQueue
类是实现优先级队列的常用类,底层实现是堆,而堆一棵特殊的完全二叉树(下面我们会重点讲解堆)- 默认情况下,
PriorityQueue
不允许插入重复的元素 PriorityQueue
不是线程安全的。如果需要在多线程环境中使用,我们可以使用PriorityBlockingQueue
,它是线程安全的优先级队列实现
2. 堆
2.1 概念
在逻辑结构上,堆是一棵完全二叉树,而在存储结构上,堆是通过一个一维数组来存储元素的。它把所有元素按完全二叉树的层序遍历顺序,存储在一个数组当中。并且在堆中,每个节点都必须满足以下两种属性之一:
小根堆(最小堆):父节点的键值必须小于或等于其子节点的键值
大根堆(最大堆):父节点的键值必须大于或等于其子节点的键值
2.2 存储方式
在上面我们提到了,“堆是通过一个一维数组来存储元素的”,而它的存储顺序就是按照完全二叉树的层序遍历来存储的,这样可以更高效的利用存储空间
因为使用数组存储堆可以方便地实现父节点到子节点的转换,所以我们可以给每一个节点记一个下标,通过下标来得到节点之间的父子关系:
我们规定根节点的下标为 0,设 i 为节点在数组中的下标,则有:
- 父节点的下标:(i - 1) / 2
- 左节点的下标: i * 2 + 1(如果得出来的数大于等于总的节点个数,则该节点没有左节点)
- 右节点的下标: i * 2 + 2(如果得出来的数大于等于总的节点个数,则该节点没有右节点)
下面是简单的对应关系图:
3. 堆的模拟实现
3.1 堆的创建
问题:把集合 {37,26,77,45,6,21,66,18,42} 创建成一个大根堆
思路:我们可以先把集合中的数据先按原始顺序排成一棵完全二叉树,接着再来调整,直至调整成为一个大根堆
那要怎么调整呢?很简单,我们回忆一下大根堆的特点:在每棵子树中,父节点始终大于子节点。顺着这个思路,我们可以得出方法:从最后一棵子树开始调整,拿根节点和两个子节点比大小,如果出现任一子节点大于根节点,就交换两者的位置,这个过程叫做“根节点的向下调整”;然后接着往前找子树,一样的套路继续调整,直至所有的父节点都大于子节点,最后调整结束,得到的就是大根堆了
干讲可能有点抽象,我们根据代码来辅助理解:
首先我们创建一个数组 elem,并设定初始容量为 10,再使用 usedSize 来记录实际容量;接着初始化数组,把要传进去的数组赋值进去
public class MyHeap {public int[] elem;public int usedSize;//构造方法public MyHeap() {this.elem = new int[10];}//初始化,把数组一个个赋值进去public void init(int[] array) {for (int i = 0; i < array.length; i++) {elem[i] = array[i];usedSize++;}}
}
现在我们就得到了一组原始数组,它是一棵待排序的二叉树,接着开始调整
//把 elem 数组中的数据调整为大根堆//时间复杂度为 O(n)public void createHeap() {//parent 为待调整树的父节点位置for (int parent = (usedSize - 1 - 1) / 2; parent >= 0 ; parent--) {shiftDown(parent, usedSize);}}//向下调整public void shiftDown(int parent, int end) {int child = 2 * parent + 1;//如果存在孩子节点,就进入循环while (child < end) {//判断最大的孩子是在左还是在右if (child + 1 < end && elem[child] < elem[child+1]) {child++;}//此时child一定是最大的孩子if (elem[child] > elem[parent]) {swap(child, parent);//交换完后再往下走parent = child;child = 2 * parent + 1;}else {//说明不需要调整,直接跳出break;}}}//交换位置public void swap(int i, int j) {int tmp = elem[i];elem[i] = elem[j];elem[j] = tmp;}
通过这么一套操作,我们就能得到大根堆,最后打印出来就是顺序就是正确的
注意:在调整以 parent 为根的树时,要保证它的左右子树都已经是堆了才能向下调整,这也是我们从最后一棵子树开始调整的原因
时间复杂度:在最坏的情况中,我们需要对每个元素进行下沉操作,下沉操作的时间复杂度是 O(log n),因为堆是一个完全二叉树,其高度是 log(n)。但总的下沉次数是 n,因此平均到每个节点上的时间复杂度就是常数时间。这导致总的时间复杂度是 O(n)
3.2 堆的插入
将元素插入到堆中,插入后依然要满足堆的性质
实现思路:
- 判断数组容量是否满了,满的话要扩容
- 把要插入的数据放在最后面,记得让 usedSize++,接着向上调整 (siftUp)
- 直到满足堆的性质
在原先的大根堆中插入 54,要求最后的结果还是大根堆
//堆的插入public void offer(int val) {if (isFull()) {//满了就扩容elem = Arrays.copyOf(elem,2 * elem.length);}//在最后一个位置添加欲插入数据elem[usedSize] = val;usedSize++;//向上调整shiftUp(usedSize - 1);}//向上调整public void shiftUp(int child) {//先找到父节点int parent = (child - 1) / 2;//如果存在父节点,就进入循环while (parent >= 0) {if (elem[child] > elem[parent]) {swap(child, parent);//交换后,继续往上,看是否需要调整child = parent;parent = (child - 1) / 2;} else {break;}}}//判满public boolean isFull() {return usedSize == elem.length;}
3.3 堆的删除
因为堆的特性,所以堆的删除我们通常指的是堆顶元素的删除,也就是说删除的是堆中最大(或者最小)的元素
实现思路:目的是为了尽可能的减少堆中元素的移动,保持堆的特性,因此我们可以采用逻辑删除
- 让堆顶元素和堆中最后一个元素交换
- 让 usedSize 减一(逻辑删除)
- 最后调整堆顶元素,向下调整
删除堆中的堆顶元素,并要求删除后依然是一个大根堆
//弹出第一个数字public int poll() {//先判断堆是不是空的if (isEmpty()) {return -1;}int old = elem[0];//记录下第一个数//把第一个和最后一个交换swap(0,usedSize - 1);//再排成大根堆usedSize--;//把最后一个数覆盖掉//第一个数向下调整,传入自己位置和堆的实际容量shiftDown(0,usedSize);//返回删除的元素return old;}public boolean isEmpty() {return usedSize == 0;}
除了 poll( ) 弹出,我们也可以来实现 peek( ),即瞥一眼堆顶元素,这个就很简单了
//瞥一眼第一个元素public int peek() {//先判断堆是不是空的if (isEmpty()) {return -1;}return elem[0];}
4. PriorityQueue
4.1 注意事项
在使用之前,记得导包
import java.util.PriorityQueue;
接下来,我们来详细讲解使用时的一些注意点:
- 在 PriorityQueue 中放置的元素必须是可比较的,若插入无法比较大小的元素,就回抛出 ClassCastException 类型转换异常
- 在使用优先队列之前,应检查队列是否为空,避免在空队列上执行删除操作导致错误
- 不能插入 null,否则会抛出 NullPointerException 空指针异常
- PriorityQueue 默认情况下是小堆,若想建成的是大堆,则需要在构造时传入比较器
- PriorityQueue 不是线程安全的。如果需要在多线程环境中使用,我们可以使用 PriorityBlockingQueue,它是线程安全的优先级队列实现
4.2 构造器介绍
-
默认构造方法:创建一个空的优先队列,默认容量为 11
public PriorityQueue()
-
带初始容量的构造方法:可以指定初始容量
public PriorityQueue(int initialCapacity)
-
带初始集合的构造方法:可以指定集合中的元素来初始化(实现了 Collection 接口的就可以接收,该集合的类型是包含 E 类型或其任何子类型的对象)
public PriorityQueue(Collection<? extends E> c)
-
带比较器的构造方法:可以使用指定的比较器来初始化(比较器决定了元素的排序方式)
public PriorityQueue(Comparator<? super E> comparator)
-
带初始集合和比较器的构造方法:可以使用指定集合中的元素和比较器来初始化
public PriorityQueue(Collection<? extends E> c, Comparator<? super E> comparator)
在这里我们重点演示一下带比较器的构造方法:
class IntCmp implements Comparator<Integer> {@Overridepublic int compare(Integer o1, Integer o2) {return o2.compareTo(o1); //调换了原来的顺序}
}
public class Test {public static void main(String[] args) {//不传入比较器PriorityQueue<Integer> priorityQueue1 = new PriorityQueue<>();priorityQueue1.offer(24);priorityQueue1.offer(52);priorityQueue1.offer(14);priorityQueue1.offer(37);System.out.println("小根堆:" + priorityQueue1);//传入比较器PriorityQueue<Integer> priorityQueue2 = new PriorityQueue<>(new IntCmp());priorityQueue2.offer(24);priorityQueue2.offer(52);priorityQueue2.offer(14);priorityQueue2.offer(37);System.out.println("大根堆:" + priorityQueue2);}
}
运行结果如下:
4.3 常用方法介绍
方法 | 描述 |
---|---|
boolean offer(E e) | 将指定元素添加到此队列中 |
E peek( ) | 返回队列头部的元素但不移除它。如果队列为空,则返回 null |
E poll( ) | 移除此队列头部的元素。如果队列为空,则返回 null |
int size( ) | 返回队列中的元素数量 |
boolean remove(Object o) | 从队列中移除指定的元素,移除成功返回 true,否则返回 false |
void clear( ) | 移除队列中的所有元素 |
boolean isEmpty( ) | 如果队列为空,则返回 true |
以上都是 PriorityQueue 的常用方法,有需要的话可以去该网址查询: PriorityQueue 的官方文档
5. 经典题型
Top-K 问题:求数据集合中前 K 个大(或者小)的元素
我们可以想想要怎么解决这个问题?最“朴素”的方法,当然是直接把数据集合排序,这样取到前 K 个大(或者小)的元素当然很简单
但是如果此时的数据量非常大,用排序法的时间复杂度一定不小,因此我们可以使用堆来求,那要怎么求呢?
力扣:最小K个数
思路:问题要求我们找到前 k 个小的元素,“前 K 个”的意思就是我们不需要给所有数排序,只要把数据集合中的前 k 个小的元素就行
题目要求取出数据中前 k 个小的元素,我们就得建大堆(有点反直觉),把前 k 个数据先建成一个大堆,接着将剩余的 N - k 个元素依次和堆顶元素比较,比堆顶元素小就换,比完后堆中剩余的 k 个元素就是题目所要求的数
class IntCmp implements Comparator<Integer> {@Overridepublic int compare(Integer o1, Integer o2) {return o2.compareTo(o1); }
}class Solution {public int[] smallestK(int[] arr, int k) {//建大堆,只放前k个数PriorityQueue<Integer> minK = new PriorityQueue<>(new IntCmp());for (int i = 0; i < k; i++) {minK.offer(arr[i]);}//比较大小,若比堆顶元素小就放进去for (int i = k; i < arr.length; i++) {if(minK.size() != 0 && arr[i] < minK.peek()) {minK.poll();minK.offer(arr[i]);}}//返回int[] ret = new int[k];for (int i = 0; i < k; i++) {ret[i] = minK.poll();}return ret;}
}
当然,有很多其他更好的解法,博主在这只是提供一个简单的思路
6. 结语
今天我们介绍了优先级队列,重点掌握它的特性,还有堆的概念以及模拟实现,明白怎么使用 PriorityQueue 的常用方法,还有 Top—K 问题,也是非常经典~
希望大家能够喜欢本篇博客,有总结不到位的地方还请多多谅解。若有纰漏,希望大佬们能够在私信或评论区指正,博主会及时改正,共同进步!
这篇关于【数据结构】优先级队列 — 堆的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!