优先级队列堆文章目录优先级队列堆前言一、堆Heap是什么二、堆的存储方式三、堆的创建四、堆的插入和删除1.堆的插入2.堆的删除五、接口介绍六、如何改为大堆六、一些题总结前言大家好啊相信大家在前面的学习中都了解了队列的概念及其基本用法那么优先级队列和他又有什么关系呢试想一下当你在沙漠中行走时天上先是掉了个馅饼再是掉了瓶水。如果像队列一样遵循先进先出FIFO的原则先pop馅饼,再pop水那就出会出现“馅饼谋杀案”这太严重了这时候数据结构提供的“优先级队列”就很不错~ 他会返回最高优先级对象并在能新添元素的基础上对优先级重新进行排序。高级吧现在让我们进入本章的学习一、堆Heap是什么先声明这不是挂羊头卖狗肉那为什么会提到“堆”呢因为优先队列是抽象数据类型没有具体代码水果而堆是最主流的底层实现苹果。现在有⼀个关键码的集合K {52013}把它的所有元素按完全二叉树的顺序存储存储在一个一维数组中根节点除外任何一个节点都小于其父亲节点也就是根节点最大的叫大根堆反之叫小根堆。堆的性质堆中某个节点的值总是不大于或不小于其父节点的值堆总是⼀棵完全二叉树。另外堆也就是Heap这个单词要记住选择题有哦~二、堆的存储方式从堆的概念可知堆是一棵完全二叉树因此可以层序的规则采用顺序方式来高效存储。为啥完全二叉树顺序存储高效捏解答对于非完全二叉树为了能够还原二叉树空间中必须要存储空节点就会导致空间利用率比较低。就像一个节点没有左孩子但是有右孩子那么在存节点的时候就需要在相应位置加null嘿这不就浪费了个空间将元素存储到数组中后可以根据⼆叉树的性质来对其进行还原。假设i为节点在数组中的下标则有如果i为0则i表示的节点为根节点否则i节点的双亲节点为 (i - 1)/2如果2 * i 1 小于节点个数则节点i的左孩子下标为2 * i 1否则没有左孩子如果2 * i 2 小于节点个数则节点i的右孩子下标为2 * i 2否则没有右孩子三、堆的创建这里以小根堆为例对于集合{991110122334}中的数据如何和创建堆看图不难发现根的左子树和右子树都满足小根堆的性质只有根本身这一节点不满足现在让我们移动它让parent标记需要调整的节点再用刚刚讲到的公式来得出他左右孩子下标▪ 发现左右孩子都存在及都size找到最小的孩子并标记为child▪ 只有左孩子那child为左孩子▪ 没孩子程序结束将parent与child比较如果▪ parent小于child调整结束▪ 否则交换parent与child即parent childchild parent*21; 交换完成之后parent继续因为可能还是不满足堆的性质需要继续向下调整重复从2开始的操作。代码实现publicvoidshiftDown(int[]array,intparent){// child先标记parent的左孩⼦因为parent可能右左没有右intchild2*parent1;intsizearray.length;while(childsize){// 如果右孩⼦存在找到左右孩⼦中较⼩的孩⼦,⽤child进⾏标记if(child1sizearray[child1]array[child]){child1;}// 如果双亲⽐其最⼩的孩⼦还⼩说明该结构已经满⾜堆的特性了if(array[parent]array[child]){break;}else{// 将双亲与较⼩的孩⼦交换inttarray[parent];array[parent]array[child];array[child]t;// parent中⼤的元素往下移动可能会造成⼦树不满⾜堆的性质因此需要继续向下调整 parentchild;childparent*21;}}}注意在调整以parent为根的二叉树时必须要满足parent的左子树和右子树已经是堆了才可以向下调整。四、堆的插入和删除1.堆的插入堆的插入总共需要两个步骤先将元素放入到底层空间中(注意空间不够时需要扩容)将最后新插入的节点向上调整直到满足堆的性质时间复杂度为O(nlogn)2.堆的删除注意堆的删除⼀定删除的是堆顶元素。具体如下将堆顶元素对堆中最后⼀个元素交换将堆中有效数据个数减少⼀个对堆顶元素进行向下调整时间复杂度为O(logn)到此为止堆的一系列知识点已经罗列完毕问题来了这东西好用是好用可在日常写代码的时候难道还需要我们自己来实现吗当然不是啦有现成的它来了此处有掌声五、接口介绍Java集合框架中提供了PriorityQueue和PriorityBlockingQueue两种类型的优先级队列PriorityQueue是线程不安全的PriorityBlockingQueue是线程安全的本文主要介绍PriorityQueue安全就是多线程同时改同一个变量不会乱数据 线程安全会错乱 线程不安全。注意事项PriorityQueue中放置的元素必须要能够比较大小不能插入无法比较大小的数据否则会抛出ClassCastException异常不能插入null对象否则会抛出NullPointerException可以插入任意多个元素其内部可以自动扩容PriorityQueue底层使用了堆数据结构PriorityQueue默认情况下是小堆——即每次获取到的元素都是最小的元素构造器功能介绍PriorityQueue()创建一个空的优先级队列默认容量为11PriorityQueue(i)创建一个初始容量为i的优先级队列但i不能1否则抛异常PriorityQueue(collection? extends Ec)用一个集合来创建优先级队列一些常用方法~函数名功能介绍boolean offer(E e)插入元素e插入成功返回true如果e对象为空抛出NullPointerException异常时间复杂度注意空间不够时候会进行扩容Epeek()获取优先级最高的元素如果优先级队列为空,返回nullE poll()移除优先级最高的元素并返回如果优先级队列为空返回nullint size()获取有效元素的个数void clear()清空boolean isEmpty()检测优先级队列是否为空空返回true六、如何改为大堆在前面我们了解到PriorityQueue默认情况下是小堆那么当我们需要大堆地时候就只能妥协了吗当然不燃起来自制比较器classCmpimplementsComparatorInteger{publicintcompare(Intergero1,Intergero2){returno2-o1;}}publicclassHello{publicstaticvoidmain(String[]args){PriorityQueueIntegerpnewPriorityQueue(newCmp());p.offer(5);p.offer(2);p.offer(0);p.offer(1);p.offer(3);System.out.println(p.peek());}}2.弄个compareTopublicclassStudent{intage;publicStudent(intage){this.ageage;}overridepublicintcompareTo(Studento){returno.age-this.age;}overridepublicStringtoString(){returnStudent{ageage};}}publicclassHello{publicstaticvoidmain(String[]args){PriorityQueueStudenttemnewPriorityQueue() tem.offer(newStudent(10));tem.offer(newStudent(20);System.out.println(tem.peek());}}来个小彩蛋猜猜这两段代码输出什么结尾公布六、一些题OK经历九九八十一难我们终于到了这一关马上就能取得真经让我们来实操一下~最小k个数总结以上就是我们今天要讲的内容啦~主要有堆的概念、创建、插入与删除以及PriorityQueue的实现和应用还有如何把小堆改成大堆还是很重要的。那今天就到先这里啦我们下期再见祝大家好梦彩蛋公布520