【数据结构】第七弹——Priority Queue
优先级队列是一种特殊的队列结构，元素出队顺序由优先级决定。本文介绍了优先级队列的概念、堆的存储方式（完全二叉树的顺序存储）及基本性质，重点讲解了堆的创建、插入和删除操作的核心算法——向上调整和向下调整，分析了建堆的时间复杂度为O(N)。文章还通过代码示例展示了如何使用堆模拟实现优先级队列，并总结了Java中PriorityQueue的特性：线程不安全、元素需可比较、自动扩容、操作时间复杂度为O(l
文章目录
一. 优先级队列(Priority Queue)
1.1 概念
前面介绍过队列，队列是一种先进先出(FIFO)的数据结构，但有些情况下，操作的数据可能带有优先级，一般出队列时，可能需要优先级高的元素先出队列，该中场景下，使用队列显然不合适
在这种情况下,数据结构应该提供两个最基本的操作，一个是返回最高优先级对象，一个是添加新的对象。这种数据结构就是优先级队列(Priority Queue)。
二. 优先队列的模拟实现
JDK1.8中的PriorityQueue底层使用了堆这种数据结构，而堆实际就是在完全二叉树的基础上进行了一些调整。
2.1 堆的概念
如果有一个关键码的集合K = {k0，k1， k2，…，kn-1}，把它的所有元素按完全二叉树的顺序存储方式存储 在一个一维数组中，并满足：Ki <= K2i+1 且 Ki<= K2i+2 (Ki >= K2i+1 且 Ki >= K2i+2) i = 0，1，2…，则称为 小堆(或大堆)。将根节点最大的堆叫做最大堆或大根堆，根节点最小的堆叫做最小堆或小根堆
堆的性质
- 堆中某个节点的值总是不大于或不小于其父亲节点的值
- 堆总是一颗完全二叉树
2.2 堆的存储方式
堆是一棵完全二叉树，因此可以层序的规则采用顺序的方式来高效存储
注意：对于非完全二叉树，则不适合使用顺序方式进行存储，因为为了能够还原二叉树，空间中必须要存储空节点，就会导致空间利用率比较低。
将元素存储到数组中后,假设i为节点在数组中的下标,则有以下性质
- 如果i为0，则i表示的节点为根节点，否则i节点的双亲节点为 (i - 1)/2
- 如果2 * i + 1 小于节点个数，则节点i的左孩子下标为2 * i + 1，否则没有左孩子
- 如果2 * i + 2 小于节点个数，则节点i的右孩子下标为2 * i + 2，否则没有右孩子
2.3 堆的创建
2.3.1 堆向下调整
举例:对于集合{ 27,15,19,18,28,34,65,49,25,37 }中的数据，如果将其创建成堆呢？
根节点的左右子树已经完全满足堆的性质，因此只需将根节点向下调整好即可
向下的过程(此处以大根堆为例)
public class TestHeap {
public int[] elem;
public int usedSize;
public TestHeap() {
this.elem = new int[10];
}
public void initElem(int[] array) {
for (int i = 0; i < array.length; i++) {
this.elem[i] = array[i];
this.usedSize++;
}
}
public void createHeap() {
for (int parent = (this.usedSize-1-1)/2; parent >= 0 ; parent--) {
siftDown(parent,this.usedSize);
}
}
/**
* @param parent 每棵子树调整的时候 的 起始位置
* @param usedSize 判断 每棵子树什么时候 调整 结束
*/
//向下调整
private void siftDown(int parent, int usedSize) {
int child = 2*parent+1;
while (child < usedSize) {
//找到左右孩子的最大值
if(child+1 < usedSize && elem[child] < elem[child+1]) {
child++;
}
if(elem[child] > elem[parent]) {
swap(elem,child,parent);
parent = child;
child = 2 * parent + 1;
}else {
break;
}
}
}
}
注意：在调整以parent为根的二叉树时，必须要满足parent的左子树和右子树已经是堆了才可以向下调整。
时间复杂度分析：
最坏的情况，从根一路比较到叶子，比较的次数为完全二叉树的高度，即时间复杂度为O(logN)
2.3.2 堆的创建
- ①.让parent 标记需要调节的节点,child 标记 parent的左孩子(注意:parent 如果有孩子一定是先有的左孩子)
- ②.如果parent 的左孩子存在,即child < size ,进行一下操作,直到parent 的左孩子不存在
2.3.3 建堆的时间复杂度
因为堆是完全二叉树，而满二叉树也是完全二叉树，此处为了简化使用满二叉树来证明(时间复杂度本来看的就是近似值，多几个节点不影响最终结果)
因此:建堆的时间复杂度是O(N)
2.4 堆的插入和删除
2.4.1 堆的插入
1.先将元素放入到底层空间中(注意:空间不够时需要扩容)
2.将最后新插入的节点向上调整,直到满足堆的性质
public void shiftUp(int child) {
// 找到child的双亲
int parent = (child - 1) / 2;
while (child > 0) {
// 如果双亲比孩子大，parent满足堆的性质，调整结束
if (array[parent] > array[child]) {
break;
}
else{
// 将双亲与孩子节点进行交换
int t = array[parent];
array[parent] = array[child];
array[child] = t;
// 小的元素向下移动，可能到值子树不满足对的性质，因此需要继续向上调增
child = parent;
parent = (child - 1) / 1;
}
}
}
2.4.2 堆的删除
注意:堆的删除一定是删除堆顶的元素
1.将堆顶的元素与堆中最后一个元素交换
2.将堆中有效数据–
3.对堆顶的元素进行向下调整直到满足堆的特性为止
2.5 用堆模拟实现优先级队列
public class MyPriorityQueue {
// 演示作用，不再考虑扩容部分的代码
private int[] array = new int[100];
private int size = 0;
public void offer(int e) {
array[size++] = e;
shiftUp(size - 1);
}
public int poll() {
int oldValue = array[0];
array[0] = array[--size];
shiftDown(0);
return oldValue;
}
public int peek() {
return array[0];
}
}
三. 常用接口介绍
3.1 Priority Queue的特性
Java集合框架中提供了PriorityQueue和PriorityBlockingQueue两种类型的优先级队列，PriorityQueue是线程不安全的PriorityBlockingQueue是线程安全的
使用 Priority Queue的注意事项:
1.使用时必须导入 Priority Queue所在的包
import java.util.PriorityQueue;
2.PriorityQueue 中放置的元素必须要能够比较大小，不能插入无法比较大小的对象，否则会抛出 ClassCastException 异常
3.不能插入 null 对象，否则会抛出 NullPointerException
4.没有容量限制，可以插入任意多个元素，其内部可以自动扩容
5.插入和删除元素的时间复杂度为 O (log₂N)
6.PriorityQueue 底层使用了堆数据结构
7.PriorityQueue 默认情况下是小堆 — 即每次获取到的元素都是最小的元素
3.2 PriorityQueue 常用接口介绍
- 1.优先级队列的构造
我们这里就只是介绍几个常见的构造方式,更详细全面的可以搜索参考文档了解
static void TestPriorityQueue(){
// 创建一个空的优先级队列，底层默认容量是11
PriorityQueue<Integer> q1 = new PriorityQueue<>();
// 创建一个空的优先级队列，底层的容量为initialCapacity
PriorityQueue<Integer> q2 = new PriorityQueue<>(100);
ArrayList<Integer> list = new ArrayList<>();
list.add(4);
list.add(3);
list.add(2);
list.add(1);
// 用ArrayList对象来构造一个优先级队列的对象
// q3中已经包含了三个元素
PriorityQueue<Integer> q3 = new PriorityQueue<>(list);
System.out.println(q3.size());
System.out.println(q3.peek());
}
在默认情况下,PriorityQueue队列是小堆,如果需要大堆需要用户提供比较器
用户自己定义的比较器:
// 用户自己定义的比较器：直接实现Comparator接口，然后重写该接口中的compare方法即可
class IntCmp implements Comparator<Integer>{
@Override
public int compare(Integer o1, Integer o2) {
return o2-o1;
}
}
public class TestPriorityQueue {
public static void main(String[] args) {
PriorityQueue<Integer> p = new PriorityQueue<>(new IntCmp());
p.offer(4);
p.offer(3);
p.offer(2);
p.offer(1);
p.offer(5);
System.out.println(p.peek());
}
}
这样创建出来就是一个大堆
- 2.插入/删除/获取优先级最高的元素
static void TestPriorityQueue2(){
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("优先级队列不为空");
}
}
关于扩容
注意:这里我们介绍的是JDK1.8中,PriorityQueue的扩容方式
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
private void grow(int minCapacity) {
int oldCapacity = queue.length;
// Double size if small; else grow by 50%
int newCapacity = oldCapacity + ((oldCapacity < 64) ?
(oldCapacity + 2) :
(oldCapacity >> 1));
// overflow-conscious code
if (newCapacity - MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity);
queue = Arrays.copyOf(queue, newCapacity);
}
private static int hugeCapacity(int minCapacity) {
if (minCapacity < 0) // overflow
throw new OutOfMemoryError();
return (minCapacity > MAX_ARRAY_SIZE) ?
Integer.MAX_VALUE :
MAX_ARRAY_SIZE;
}
优先级队列的扩容说明:
①.如果容量小于64是,按照oldCapacity 的 2 倍方式扩容的
②.如果容量大于等于 64，是按照 oldCapacity 的 1.5 倍方式扩容的
③.如果容量超过 MAX_ARRAY_SIZE，按照 MAX_ARRAY_SIZE 来进行扩容
3.3 OJ题-top-k问题
class Solution {
class IntCmp implements Comparator<Integer> {
@Override
public int compare(Integer o1, Integer o2) {
return o2.compareTo(o1);
}
}
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 IntCmp());
//k*logK
for (int i = 0; i < k; i++) {
priorityQueue.offer(arr[i]);
}
//(n-k)*logK
for (int i = k; i < arr.length; i++) {
int peekVal = priorityQueue.peek();
if(arr[i] < peekVal) {
priorityQueue.poll();
priorityQueue.offer(arr[i] );
}
}
for (int i = 0; i < k; i++) {
ret[i] = priorityQueue.poll();
}
return ret;
}
}
四. 堆的应用
4.1 PriorityQueue的实现
用堆作为底层结构封装优先级队列
4.2 堆排序
堆排序即利用堆的思想来进行排序
步骤
①.建堆
- 升序:建大堆
- 降序:建小堆
②.利用堆删除思想进行排序
建堆和堆删除中都用到了向下调整,因此掌握了向下调整就可以完成堆排序
4.3 Top-k问题
TOP-K问题：即求数据集合中前K个最大的元素或者最小的元素，一般情况下数据量都比较大
TOP-K问题：即求数据集合中前K个最大的元素或者最小的元素，一般情况下数据量都比较大
思路:
1.用数据集合中前K个元素来建堆
- 前K个最大的元素,则建小堆
- 前K个最小的元素,则建大堆
- 用剩余的N-K个元素依次与堆顶元素来比较,不满足则替换堆顶元素
将剩余的N-K个元素依次与堆顶元素比完之后,堆中剩余的K个元素就是所求的前K个最小或者最大的元素
Top-K具体实现
public int[] smallestK(int[] arr, int k) {
PriorityQueue<Integer> priorityQueue = new PriorityQueue<>();
//O(N*logN)
for (int i = 0; i < arr.length; i++) {
priorityQueue.offer(arr[i]);
}
//O(K*logN)
int[] ret = new int[k];
for (int i = 0; i < k; i++) {
ret[i] = priorityQueue.poll();
}
return ret;
}
DAMO开发者矩阵，由阿里巴巴达摩院和中国互联网协会联合发起，致力于探讨最前沿的技术趋势与应用成果，搭建高质量的交流与分享平台，推动技术创新与产业应用链接，围绕“人工智能与新型计算”构建开放共享的开发者生态。
更多推荐
16
0- 0
已为社区贡献1条内容
所有评论(0)