【java数据结构-优先级队列向下调整Topk问题，堆的常用的接口详解】

本文主要是介绍【java数据结构-优先级队列向下调整Topk问题，堆的常用的接口详解】，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

在这里插入图片描述

🌈个人主页：努力学编程’
⛅个人推荐：基于java提供的ArrayList实现的扑克牌游戏 |C贪吃蛇详解
⚡学好数据结构，刷题刻不容缓：点击一起刷题
🌙心灵鸡汤：总有人要赢，为什么不能是我呢
在这里插入图片描述

相信大家对于队列的理解是比较熟悉的，队列是一种先进先出的数据结构，但是我们在日常项目的开发中往往需要对于一些数据的处理是要求所使用的数据结构处理数据时必须有一定的优先级的，比如你在打游戏的时候，字节给你打入职电话，那么手机一定会优先处理电话的业务，或者在你的学生时代，一定经历过老师让学习好的同学先挑座位，类似与这种情况，我们引出一个新的数据结构优先级队列-堆

🌈堆的定义：

堆是一种特殊的树形数据结构，它满足堆属性：对于堆中任意节点 i，父节点的值小于等于（或大于等于）其子节点的值。根据这个属性，可以将堆分为最大堆和最小堆。在最大堆中，父节点的值大于等于其子节点的值；在最小堆中，父节点的值小于等于其子节点的值。

堆通常用于实现优先级队列，因为堆能够快速找到具有最高（或最低）优先级的元素。常见的堆有二叉堆和斐波那契堆，它们在插入和删除操作的时间复杂度上有所不同，但都能保持堆属性。

大根堆：

顾名思义：根节点其实是整个完全二叉树的最大值的节点，他的左孩子结点和右孩子节点都比他要小，同时要保证整棵树是大根堆那么每棵子树也必须得是大根堆，这样才可以构成一个完整的大根堆结构。

在这里插入图片描述

小根堆：

有了大根堆理解，我们去学习小根堆就轻松多了，每棵子树的根节点都是这棵子树中的值最小的，这样所有的子树就构成了整个小根堆。
有了小根堆和大根堆的概念，我们后面可以尝试自己实现一个小根堆和大根堆，后面会给大家实现。请大家牢记这些基本知识。

🌝堆的创建

讲了堆的一些基本知识，相信大家都和我一样，手痒难耐，非常想自己手搓一个堆，但是在这之前我们必须要先了解一个知识点向下调整，这是我们实现队列的基本要求。

向下调整：

在这里插入图片描述
1. 让parent标记需要调整的节点，child标记parent的左孩子(注意：parent如果有孩子一定先是有左孩子)

2. 如果parent的左孩子存在，即:child < size，进行以下操作，直到parent的左孩子不存在parent右孩子是否存在，存在找到左右孩子中最小的孩子，让child进行标将parent与较小的孩子child比较，如果：

parent小于较小的孩子child，调整结束，
否则：交换parent与较小的孩子child，交换完成之后，parent中大的元素向下移动，可能导致子树不满足对的性质，因此需要继续向下调整，即parent = child；child = parent*2+1; 然后继续2。

具体的过程建议大家，在纸上先自己实现一下，这里把整个过程也给大家：
在这里插入图片描述

public void shiftDown(int[]array,int parent){int child=2*parent+1;int size= array.length;while(child<size){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=child;child=parent*2+1;}}

好了掌握了向下调整的知识点，我们就可以自己手搓一个堆了，我们实现的代码是比较简单的。针对每个节点我们都使用，向下调整的逻辑，就可以实现大根堆或者小根堆，

public static void createHeap(int[] array) {
// 找倒数第一个非叶子节点，从该节点位置开始往前一直到根节点，遇到一个节点，应用向下调整
int root = ((array.length-2)>>1);
for (; root >= 0; root--) {
shiftDown(array, root);
}
public void shiftDown(int[]array,int parent){int child=2*parent+1;int size= array.length;while(child<size){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=child;child=parent*2+1;}}
}

🚴堆的时间复杂度：

因为初始化堆，是每个数据向下冒泡，每一层冒泡的次数不同，最高层冒泡的次数最多为logn,最底层为1次，设共有h层（h=logn) , 时间复杂度的计算为：1h+2(h-1)+4(h-2)+…+2^(h-1)1

即【节点数所在层数】的累加，如2（h-1）即第二层有两个节点，因为在第二层，所以会冒泡h-1次

可以转化为通项：
k从0到h-1的累加用错项相减法求可以得到O()，即O（）即O（n)
关于调整堆/删除堆：

因为在调整的时候，每调整/删除一次，树的节点就会少一个（跑到有序堆去了），然鹅每次调整的时候，是从下往上冒泡的，所以调整的次数即当前树的层数，那怎么确定当前树的层数呢，直接对当前节点取对数就好了，每一个节点都要进行这样的操作，所以操作的次数是log(n-1)+log(n-2)+…+log2+log1=log(n-1)!=nlogn

故时间复杂度为O（nlogn)

故整个堆排序时间复杂度取大的O（nlogn)

⛅堆的插入和删除

插入：

大家有没有想过在堆里面如何添加节点呢，整个过程大致分为两个步骤，

将待插入的节点放到二叉树的最后一个叶子节点
从待插入的节点开始依次进行shiftUp向上调整

在这里插入图片描述

具体向上调整代码如何实现，这里也给大家一段代码

public void shiftUp(int[] array,int child){//这里模拟的是大根堆的情况int parent=(child-1)/2;while(child>0){if(array[parent]>array[child]){break;}else {int t=array[child];array[parent]=array[child];array[child]=t;child=parent;parent=(child-1)/2;}}}

删除：

对于堆的删除是十分重要的，想想我们在文章开始的时候，是不是说过，堆的底层逻辑是一种线性结构，本质上我们可以使用数组实现，那么如果把他转化为数组的时候，我们知道数组的元素其实是不能删除掉的，只能对数据进行覆盖，来完成元素的删除。堆在这里也是一样。

堆删除的具体步骤如下：

将待删除的元素与二叉树的最后一个叶子结点进行交换
将堆的底层数组内的有效数据个数减一
把整个二叉树进行向下调整，重新调整二叉树的结构实现大根堆或者小根堆

在这里插入图片描述

 public int poll() {if(isEmpty()) {return -1;}int old = elem[0];swap(0,usedSize-1);usedSize--;siftDown(0,usedSize);return old;}

有关堆的一些常见接口介绍：

在java中我们并不需要自己去实现堆，java是一门高级语言，我们只需要知道每种重要的数据结构底层是如何实现的，然后我们直接使用系统为我们提供的结构就好了。

Java集合框架中提供了PriorityQueue和PriorityBlockingQueue两种类型的优先级队列，PriorityQueue是线程不安全的，PriorityBlockingQueue是线程安全的，这里主要介绍PriorityQueue。

在这里插入图片描述
关于PriorityQueue的使用要注意：

使用时必须导入PriorityQueue所在的包，即：

java import java.util.PriorityQueue;

PriorityQueue中放置的元素必须要能够比较大小，不能插入无法比较大小的对象，否则会抛出ClassCastException异常
不能插入null对象，否则会抛出NullPointerException
没有容量限制，可以插入任意多个元素，其内部可以自动扩容
插入和删除元素的时间复杂度为O( $l o g n$ )
PriorityQueue底层使用了堆数据结构
PriorityQueue默认情况下是小堆—即每次获取到的元素都是最小的元素

当然我们也要熟悉对于堆的一些基础操作：

在这里插入图片描述

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("优先级队列不为空");
}
}

优先级队列的扩容说明：

如果容量小于64时，是按照oldCapacity的2倍方式扩容的
如果容量大于等于64，是按照oldCapacity的1.5倍方式扩容的
如果容量超过MAX_ARRAY_SIZE，按照MAX_ARRAY_SIZE来进行扩容

堆的应用-TopK问题

对于Top-K问题，能想到的最简单直接的方式就是排序，但是：如果数据量非常大，排序就不太可取了(可能数据都
不能一下子全部加载到内存中)。最佳的方式就是用堆来解决，基本思路如下：

我们最先想到的，就是创建一个小根堆把前k个元素放进去，然后接着遍历数组将较小的元素换进去，最后将堆的元素放到一个数组中返回这个数组就好。

class IntCmp implements Comparator<Integer> {@Overridepublic int compare(Integer o1, Integer o2) {return o2.compareTo(o1);}
}
public class Test {/*虽然 通过了 但是 不是非常好的解决方案*/public static int[] smallestK1(int[] arr, int k) {PriorityQueue<Integer> minHeap = new PriorityQueue<>();for (int i = 0; i < arr.length; i++) {minHeap.offer(arr[i]);}int[] tmp = new int[k];for (int i = 0; i < k; i++) {int val = minHeap.poll();tmp[i] = val;}return tmp;}

这段代码虽然可以提交成功，但是并非是最优的解法，最规范的解法，是这样的：

用数据集合中前K个元素来建堆
前k个最大的元素，则建小堆
前k个最小的元素，则建大堆
用剩余的N-K个元素依次与堆顶元素来比较，不满足则替换堆顶元素
将剩余N-K个元素依次与堆顶元素比完之后，堆中剩余的K个元素就是所求的前K个最小或者最大的元素。

class IntCmp implements Comparator<Integer> {@Overridepublic int compare(Integer o1, Integer o2) {return o2.compareTo(o1);}
}
class Solution {public static int[] smallestK(int[] arr, int k) {int[] tmp = new int[k];if(k == 0) {return tmp;}PriorityQueue<Integer> maxHeap = new PriorityQueue<>(new IntCmp());//1.把前K个元素放进堆中for (int i = 0; i < k; i++) {maxHeap.offer(arr[i]);}//2.遍历剩下的N-K个元素for (int i = k; i < arr.length; i++) {int val = maxHeap.peek();if(val > arr[i]) {maxHeap.poll();maxHeap.offer(arr[i]);}}for (int i = 0; i < k; i++) {tmp[i] = maxHeap.poll();}return tmp;}
}