Java数据结构——优先级队列PriorityQueue
目录
一、优先级队列
1.1 概念
我们之前学过队列，队列是一种先进先出的数据结构。但在有些场景中，我们并不是完全按照先后顺序来处理事件，比如：在玩游戏的时候，有电话打进来，我们要优先去处理电话。游戏比电话先开始，但此时我们选择优先处理电话，所以在某些情况下，操作的事务或者数据有优先级，出队列的时候，我们需要让优先级高的元素先出队列。
在这种情况下，数据结构应该提供两个最基本的操作，一个是返回最高优先级对象，一个是添加新对象。这种数据结构就是优先级队列（PriorityQueue）。
二、优先级队列的模拟实现
PriorityQueue底层使用了堆这种数据结构，而堆实际就是在完全二叉树的基础上进行了一些调整
2.1 堆的概念
如果有一个关键码的集合K={k0,k1,k2…kn-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为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不满足小根堆的性质，所以我们需要把根节点向下调整到正确的位置
向下调整的过程：
- 让parent标记需要调整的节点，child标记parent的左孩子（注意：如果parent节点有孩子一定让child先标记左孩子）
- 如果parent的左孩子存在，则进入以下循环，直到孩子不存在
判断parent右孩子是否存在，如果存在则找到左右孩子中最小的孩子，让child标记
将parent与较小的孩子child比较，如果：
1.parent小于较小的孩子 child，调整结束；
2.parent大于较小的孩子child，交换parent和child。parent向下移动后，可能会破坏原来的堆结构，所以需要继续向下调整，让parent=child；child=parent*2+1（parent节点=child节点，child=parent节点的左孩子）
public void shiftDown(int[] array, int parent) {
// child先标记parent的左孩子，因为parent可能右左没有右
int child = 2 * parent + 1;
int size = array.length;
while (child < size) {
// 如果右孩子存在，找到左右孩子中较小的孩子,用child进行标记
if(child+1 < size && array[child+1] < array[child]){
child += 1;
} // 如果双亲比其最小的孩子还小，说明该结构已经满足堆的特性了
if (array[parent] <= array[child]) {
break;
}else{
// 将双亲与较小的孩子交换
int t = array[parent];
array[parent] = array[child];
array[child] = t;
// parent中大的元素往下移动，可能会造成子树不满足堆的性质，因此需要继续向下调整
parent = child;
child = parent * 2 + 1;
}
}
}注意：在调整以parent为跟的二叉树，必须满足parent的左子树和右子树已经是堆了才可以向下调整。
时间复杂度：
最坏的情况就是从根节点一直调整到叶子结点，比较的次数就是为完全二叉树的高度，时间复杂度为O(log2n)
2.3.2 堆的创建
我们刚刚讨论的把根节点向下调整的情况，是以根节点的左右树已经满足堆的特性的前提，那么面对普通的序列{1,5,3,8,7,6}，根节点左右子树不满足堆的特性，我们如何调整
我们要找到倒数第一个非叶子节点，从该节点开始向下调整，调整结束后往前找到下一个节点，接着向下调整，一直找到根节点，向下调整
public void createHeap(int[] array) {
// 找倒数第一个非叶子节点，从该节点位置开始往前一直到根节点，遇到一个节点，应用向下调整
int root = ((array.length-2)>>1);
for (; root >= 0; root--) {
shiftDown(array, root);
}
}
public void shiftDown(int[] array, int parent) {
// child先标记parent的左孩子，因为parent可能右左没有右
int child = 2 * parent + 1;
int size = array.length;
while (child < size) {
// 如果右孩子存在，找到左右孩子中较小的孩子,用child进行标记
if(child+1 < size && array[child+1] < array[child]){
child += 1;
} // 如果双亲比其最小的孩子还小，说明该结构已经满足堆的特性了
if (array[parent] <= array[child]) {
break;
}else{
// 将双亲与较小的孩子交换
int t = array[parent];
array[parent] = array[child];
array[child] = t;
// parent中大的元素往下移动，可能会造成子树不满足堆的性质，因此需要继续向下调整
parent = child;
child = parent * 2 + 1;
}
}
}2.4 堆的插入和删除
2.4.1 堆的向上调整
以大根堆为例，标记要向上调整的节点为child，找到双亲节点parent，如果双亲节点比孩子大，则不需要调整，调整结束。如果双亲节点比孩子小，孩子与双亲节点交换。只要child>0，child=parent，parent=(child-1)/2,继续调整。
public void shiftUp(int[] array,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. 对堆顶元素进行向下调整
public void poll(int array[]) {
array[0] = array[--size];
shiftDown(array,0);
}
public void shiftDown(int[] array, int parent) {
// child先标记parent的左孩子，因为parent可能右左没有右
int child = 2 * parent + 1;
int size = array.length;
while (child < size) {
// 如果右孩子存在，找到左右孩子中较小的孩子,用child进行标记
if(child+1 < size && array[child+1] < array[child]){
child += 1;
} // 如果双亲比其最小的孩子还小，说明该结构已经满足堆的特性了
if (array[parent] <= array[child]) {
break;
}else{
// 将双亲与较小的孩子交换
int t = array[parent];
array[parent] = array[child];
array[child] = t;
// parent中大的元素往下移动，可能会造成子树不满足堆的性质，因此需要继续向下调整
parent = child;
child = parent * 2 + 1;
}
}三、常用接口介绍
3.1 PriorityQueue的特性
Java集合框架中提供了PriorityQueue和PriorityBlockingQueue两种类型的优先级队列，PriorityQueue是线程不安全的，PriorityBlockingQueue是线程安全的，本文主要介绍PriorityQueue。
关于PriorityQueue的使用要注意：
1. 使用时必须导入PriorityQueue所在的包：
2. PriorityQueue中放置的元素必须要能够比较大小，不能插入无法比较大小的对象，否则会抛出ClassCastException异常
3. 不能插入null对象，否则会抛出NullPointerException
4. 没有容量限制，可以插入任意多个元素，其内部可以自动扩容
5. 插入和删除元素的时间复杂度为O(log2N)
6. PriorityQueue底层使用了堆数据结构
7. PriorityQueue默认情况下是小堆---即每次获取到的元素都是最小的元素
3.2 PriorityQueue常用接口介绍
3.2.1 优先级队列的构造
| 构造器 | 功能介绍 |
| PriorityQueue() | 创建一个空的优先级队列，默认容量是11 |
| PriorityQueue(int intialCapacity) | 创建一个初始容量为initialCapacity的优先级队列，初始容量不能小于1，否则会抛出异常 |
| PriorityQueue(Collection<? extends E> c) | 用一个集合来创建优先级队列 |
注意：默认情况PriorityQueue是小堆，如果需要大堆，用户则要提供比较器
class IntCmp implements Comparator<Integer> {
@Override
public int compare(Integer o1, Integer o2) {
return o2-o1;
}
}
public class TestPriorityQueue {
public 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()); // 5
}
}
此时创建出来的就是大堆了，出堆的节点为5
3.2.2 常用方法
| 函数名 | 功能介绍 |
| boolean offer(E e) | 插入元素e，插入成功返回true，如果e对象为空，抛出异常，时间复杂度O(log2N)，注意：空间不够时会自动扩容 |
| E peel() | 获取优先级最高的元素，如果优先级队列为空，返回null |
| E poll() | 移除优先级最高的元素并返回，如果优先级队列为空，返回null |
| int size() | 获取有效元素的个数 |
| void clear() | 清空 |
| boolean isEmpty() | 检测优先级队列是否为空，空则返回true |
北京人形旗下天工造物具身智能开源社区，聚焦具身天工与慧思开物两大平台
更多推荐
23
0- 0
已为社区贡献4条内容
所有评论(0)