数据结构-6.优先级队列
数据结构-6.优先级队列
本篇博客给大家带来的是 优先级队列(堆) 的知识点, 其中包括 建堆时间复杂度的求解, 堆的向下调整算法, 向上调整算法, 堆的插入,删除操作 ...... 至于 PriorityQueue的扩容, 面试题 top-k问题 以及 堆排序 在后序会专门出一篇文章.
文章专栏: Java-数据结构
若有问题 评论区见
欢迎大家点赞 评论 收藏 分享
如果你不知道分享给谁,那就分享给薯条.
1.优先级队列
1.1概念
前面介绍过队列， 队列是一种先进先出 (FIFO) 的数据结构 ，但有些情况下， 操作的数据可能带有优先级，一般出队 列时，可能需要优先级高的元素先出队列 ，该中场景下，使用队列显然不合适，比如：在手机上玩游戏的时候，如 果有来电，那么系统应该优先处理打进来的电话；初中那会班主任排座位时可能会让成绩好的同学先挑座位。
在这种情况下， 数据结构应该提供两个最基本的操作，一个是返回最高优先级对象，一个是添加新的对象 。这种数据结构就是优先级队列 (Priority Queue) 。
2. 优先级队列的模拟实现
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 } 中的数据，如果将其创建成堆呢？
按照层序遍历的顺序画出二叉树
根节点的左右子树已经完全满足堆的性质，若要创建小根堆或者大根堆只需将节点向下调整好即可 。
向下调整:
1. 让 parent 标记为需要调整的节点, child 标记为parent 的左孩子 (注意: parent如果 有孩子一定是先有左孩子), size为二叉树的节点总个数. (parent child 都是节点下标, 下图中 p 表示parent, c 表示 child)
2. 如果 parent 的左孩子存在, 即: child < size . 进行下述操作, 直到 child 不存在.
parent 右孩子是否存在，存在的话 找到左右孩子中最小的孩子并 让child 标记较小的那个节点.
将 parent 与较小的孩子 child 比较，如果：
parent 小于较小的孩子 child ，调整结束
否则：交换 parent 与较小的孩子 child ，交换完成之后， parent 中大的元素向下移动，可能导致子
树不满足小根堆的性质，因此需要继续向下调整，即 parent = child； child = parent*2+1; 然后继续第 2步 。
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;
}
}
}时间复杂度分析：
最坏的情况 即图示的情况， 从根一路比较到叶子，比较的次数为完全二叉树的高度，即时间复杂度为 O(log n) -> 底数为2.
注意：在调整以 parent 为根的二叉树时，必须要满足 parent 的左子树和右子树已经是堆了才可以向下调整。 那如果是一颗普通的二叉树, 怎么将其调整成 小根堆 或者 大根堆呢?
2.3.2 堆的创建
刚刚因为 根节点的左右子树都已满足是小根堆 所以从 根节点 开始 向下调整.
再次以集合{ 27,15,19,18,28,34,65,49,25,37 } 为例子, 在其左右子树不满足大根堆的情况下, 将其调整成大根堆. 既然左右子树都不是大根堆的时候无法从根节点开始调整, 那就从最后一个节点开始调整.
//建大堆
public void createHeap() {
//parent为最后一个非叶子节点的下标,从这开始向下调整,调整好一次就--.
for (int parent = (usedSize-1-1)/2; parent >= 0; parent--) {
shiftDown(parent,usedSize);
}
}
//向下调整算法
public void shiftDown(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(child,parent);
//继续往下考虑是否需要交换
parent = child;
child = (parent*2) + 1;
}else {
//到这里,说明本身就是大根堆了.
break;
}
}
}
//通过下标交换对应的元素值
private void swap(int i,int j) {
int tmp = elem[i];
elem[i] = elem[j];
elem[j] = tmp;
}2.3.3 建堆的时间复杂度
因为堆是完全二叉树，而满二叉树也是完全二叉树，此处为了简化使用满二叉树来证明 ( 时间复杂度本来看的就是近似值，多几个节点不影响最终结果) ：
因此, 建堆的时间复杂度为 O(n)
2.4 堆的插入与删除
2.4.1 堆的插入
堆的插入总共需要两个步骤：
1. 先将元素放入到底层空间中 ( 注意：空间不够时需要扩容 )
2. 将最后新插入的节点向上调整，直到满足堆的性质
//插入堆中的元素
public void offer(int val) {
//判断堆满了没,满了就扩二倍
if(isFull()) {
this.elem = Arrays.copyOf(elem,elem.length*2);
}
elem[usedSize] = val;//放到堆的末位
//插入元素后为了保证它还是大根堆,所以写一个向上调整算法.
shiftUp(usedSize);
}
private void shiftUp(int child) {
int parent = (child-1)/2;
while(child > 0) {
if(elem[child] > elem[parent]) {
swap(child,parent);
child = parent;
parent = (child-1)/2;
}else {
break;
}
}
}
//检查堆容量是否满了
private boolean isFull() {
return usedSize == elem.length;
}2.4.2 堆的删除
注意：堆的删除一定删除的是堆顶元素。 具体如下：
1. 将堆顶元素对堆中最后一个元素交换
2. 将堆中有效数据个数减少一个
3. 对堆顶元素进行向下调整
//向下调整算法
public void shiftDown(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(child,parent);
//继续往下考虑是否需要交换
parent = child;
child = (parent*2) + 1;
}else {
//到这里,说明本身就是大根堆了.
break;
}
}
}
//通过下标交换对应的元素值
private void swap(int i,int j) {
int tmp = elem[i];
elem[i] = elem[j];
elem[j] = tmp;
}
//堆的头删法
public int poll() {
//保存要删除的元素
int tmp = this.elem[0];
//交换首尾元素
swap(0,usedSize-1);
usedSize--;
shiftDown(0,usedSize);
return tmp;
}3. 常用接口介绍
3.1 PriorityQueue的特性
Java 集合框架中提供了 PriorityQueue 和 PriorityBlockingQueue 两种类型的优先级队列， PriorityQueue 是线 程不安全的， PriorityBlockingQueue 是线程安全的 ，本文主要介绍 PriorityQueue
1. PriorityQueue 中放置的 元素必须要能够比较大小，不能插入无法比较大小的对象，否则会抛出
ClassCastException 异常
2. 不能 插入 null 对象，否则会抛出 NullPointerException
3. 没有容量限制，可以插入任意多个元素，其内部可以自动扩容
4. 插入和删除元素的时间复杂度为
5. PriorityQueue 底层使用了堆数据结构
6. PriorityQueue 默认情况下是小堆 --- 即每次获取到的元素都是最小的元素
3.2 PriorityQueue常用接口介绍
1. 优先级队列的构造
自行实现即可, 具体功能看源码.
// 创建一个空的优先级队列，底层默认容量是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. 插入 / 删除 / 获取优先级最高的元素
腾讯云开发者
