文章目录一、认识优先级队列1.1 什么是优先级队列1.2 优先级队列的底层堆堆的定义与分类堆的性质堆的存储方式二、堆的操作实现2.1 堆的创建createHeap2.2 堆的向下调整shiftDown2.3 堆的插入offer2.4 堆的向上调整shiftUp2.5 堆的删除poll三、Java中的PriorityQueue详解3.1 PriorityQueue的特性3.2 PriorityQueue的常用构造器3.3 自定义比较器实现大堆3.4 PriorityQueue的常用方法四、堆的经典应用4.1 堆排序4.2 Top-K问题思路一、认识优先级队列1.1 什么是优先级队列优先级队列是一种特殊的队列它不再遵循“先进先出”的规则而是按照元素的优先级来决定出队顺序优先级高的元素先出队优先级低的元素后出队。它最核心的两个操作是返回最高优先级的元素添加新的元素1.2 优先级队列的底层堆JDK1.8中PriorityQueue的底层采用堆这种数据结构实现。堆并非全新的数据结构而是在完全二叉树基础上增加了规则约束的特殊结构。堆的定义与分类假设有一个关键码集合K{k0, k1, k2, …, kn-1将其按完全二叉树的顺序存储在一维数组中若满足以下条件则称为堆小堆小根堆每个节点的值都不大于其左右孩子的值即Ki K2i1且Ki K2i2根节点是整个堆中最小的元素。大堆大根堆每个节点的值都不小于其左右孩子的值即Ki K2i1且Ki K2i2根节点是整个堆中最大的元素。堆的性质堆中任意节点的值总是满足“不大于小堆”或“不小于大堆”其父节点的值。堆一定是一棵完全二叉树这也是堆能高效用数组存储的关键。堆的存储方式由于堆是完全二叉树我们可以通过数组按层序顺序存储堆无需存储空节点空间利用率极高。假设数组下标为 i 则节点间的关系满足若i0则该节点是根节点否则其父节点下标为(i-1)/2。若2i1 节点总数左孩子下标为2i1否则无左孩子。若2i2 节点总数右孩子下标为2i2否则无右孩子。二、堆的操作实现要实现堆关键要掌握向下调整、向上调整两个算法在此基础上可完成堆的创建、插入和删除。2.1 堆的创建createHeap对于任意无序数组我们从倒数第一个非叶子节点开始依次向前对每个节点执行向下调整最终可将数组调整为堆。倒数第一个非叶子节点的下标为(size - 1 -1) / 2代码实现publicvoidcreateHeap(){for(intparent(size-1-1)/2;parent0;parent--){shiftDown(parent);}}时间复杂度通过数学推导错位相减建堆的总操作步数约为(n)因此时间复杂度为O(n)2.2 堆的向下调整shiftDown向下调整的前提是待调整节点的左、右子树已满足堆的性质。以大堆为例先找到最后一棵子树的根节点parent (len - 1 - 1 ) / 2使用for循环初始parent的位置是(len - 1 - 1 ) / 2每次只需要让parent--来调整前一棵树最终parent0结束循环。向下调整若右孩子存在比较左右孩子大小让child标记更大的孩子。比较parent和child的值若parent值更大满足大堆性质调整结束。否则交换parent和child的值之后parent指向childchild指向新parent的左孩子继续调整。child的边界是数组的size大小代码实现大堆privatevoidshiftDown(intparent){intchildparent*21;//让child指向左孩子while(childsize){if(child1sizeelem[child]elem[child1]){child;//让child指向最大的子节点}if(elem[child]elem[parent]){//交换inttmpelem[child];elem[child]elem[parent];elem[parent]tmp;//向下改变引用parentchild;childparent*21;}else{break;}}}时间复杂度最坏情况需从根节点调整到叶子节点比较次数为堆的高度完全二叉树高度为log2n)因此时间复杂度为O(log2n)。2.3 堆的插入offer堆的插入需保证插入后仍满足堆性质将新元素放入数组末尾需要进行扩容处理再进行向上调整。代码实现大堆publicvoidpush(intval){if(isFull()){elemArrays.copyOf(elem,elem.length*2);}elem[size]val;shiftUp(size-1);}2.4 堆的向上调整shiftUp用child标记新插入节点向上调整计算parent(child - 1) / 2。比较parent和child的值若parent满足堆性质大堆中parent更大调整结束。否则交换parent和childchild指向parent继续向上调整。privatevoidshiftUp(intchild){intparent(child-1)/2;while(parent0){if(elem[child]elem[parent]){swap(child,parent);childparent;parent(child-1)/2;}else{break;}}}2.5 堆的删除poll堆的删除有一个严格规则只能删除堆顶元素也就是优先级最高的元素。将堆顶元素数组下标0与数组最后一个元素交换。有效元素个数减1相当于删除了原堆顶元素。此时只有0下标不满足堆性质只需要对0下标元素执行向下调整一次就可以恢复堆性质。publicintpoll(){if(size0)return-1;inttopelem[0];//交换首尾swap(0,size-1);size--;shiftDown(0);returntop;}三、Java中的PriorityQueue详解Java集合框架提供了PriorityQueue线程不安全和PriorityBlockingQueue线程安全日常开发中PriorityQueue使用更广泛。3.1 PriorityQueue的特性包导入使用前需导入java.util.PriorityQueue。元素可比性队列中元素必须能比较大小否则插入时抛出ClassCastException不能插入null否则抛出NullPointerException。容量与扩容无固定容量可自动扩容扩容规则容量64时按“原容量的2倍”扩容近似2倍。容量≥64时按“原容量的1.5倍”扩容oldCapacity 1。若容量超过Integer.MAX_VALUE - 8整数的最大值则按Integer.MAX_VALUE扩容。时间复杂度插入offer和删除poll操作均为O(log2n)。默认堆类型默认是小堆若需大堆需自定义比较器实现Comparator接口。3.2 PriorityQueue的常用构造器构造器功能说明PriorityQueue()创建空队列默认容量11PriorityQueue(int initialCapacity)创建指定初始容量的空队列容量≥1否则抛异常PriorityQueue(Collection? extends E c)用集合c的元素创建队列// 1. 默认构造器小堆容量11PriorityQueueIntegerq1newPriorityQueue();// 2. 指定初始容量容量100PriorityQueueIntegerq2newPriorityQueue(100);// 3. 用集合创建ArrayListIntegerlistnewArrayList();list.add(4);list.add(3);list.add(2);list.add(1);PriorityQueueIntegerq3newPriorityQueue(list);System.out.println(q3大小q3.size());// 输出4System.out.println(q3堆顶q3.peek());// 输出1小堆3.3 自定义比较器实现大堆PriorityQueue默认是小堆若需大堆需在构造时传入自定义Comparator重写compare方法小堆compare(o1, o2) return o1 - o2o1小则返回负数o1优先级高。大堆compare(o1, o2) return o2 - o1o2大则返回正数o2优先级高。大堆// 自定义大堆比较器classBigHeapComparatorimplementsComparatorInteger{Overridepublicintcompare(Integero1,Integero2){// o2 - o1o2大则返回正数o2优先级高returno2-o1;//存在拆箱机制}}publicclassBigHeapDemo{publicstaticvoidmain(String[]args){PriorityQueueIntegerbigHeapnewPriorityQueue(newBigHeapComparator());bigHeap.offer(4);bigHeap.offer(3);bigHeap.offer(5);bigHeap.offer(1);System.out.println(大堆堆顶bigHeap.peek());// 输出5}}3.4 PriorityQueue的常用方法方法名功能说明boolean offer(E e)插入元素e成功返回true失败抛异常E peek()获取堆顶元素空队列返回nullE poll()删除并返回堆顶元素空队列返回nullint size()返回有效元素个数void clear()清空队列boolean isEmpty()判断队列是否为空空返回true四、堆的经典应用堆的应用非常广泛除了实现优先级队列还有堆排序、Top-K问题等经典场景。4.1 堆排序建堆升序排序建大堆每次将最大元素放到末尾。降序排序建小堆每次将最小元素放到末尾。利用堆删除思想排序将堆顶元素最大/最小与数组末尾元素交换有效长度减1。对新堆顶执行向下调整恢复堆性质。重复上述步骤直到有效长度为1。示例升序排序建大堆privatestaticvoidshiftDown(int[]arr,intparent,intlength){intchildparent*21;while(childlength){if(child1lengtharr[child]arr[child1])child;if(arr[parent]arr[child]){swap(arr,parent,child);parentchild;childparent*21;}else{break;}}}privatestaticvoidcreateHeap(int[]arr){for(intparent(arr.length-2)/2;parent0;parent--){shiftDown(arr,parent,arr.length);}}publicstaticvoidheapSort(int[]arr){createHeap(arr);intendarr.length-1;while(end0){swap(arr,0,end);shiftDown(arr,0,end);end--;}}原数组[5, 11, 7, 2, 3, 17]建大堆[17, 11, 7, 2, 3, 5]。堆顶17与末尾5交换[5, 11, 7, 2, 3, 17]有效长度5调整堆为[11, 5, 7, 2, 3, 17]。堆顶11与末尾3交换[3, 5, 7, 2, 11, 17]有效长度4调整堆为[7, 5, 3, 2, 11, 17]。重复操作最终得到升序数组[2, 3, 5, 7, 11, 17]。注意shiftDown必须把数组长度添加到参数列表因为在建好堆以后的排序过程中每出队一个就认为这个数组的长度逻辑上-1但事实是数组长度不变如果没有参数每次都会把整个数组的长度作为待排序的数组的长度。4.2 Top-K问题Top-K问题是指从海量数据中找出前K个最大或最小的元素数据量可能大到无法全部加载到内存用堆解决是最优方案。思路以找前K个最小值为例排序后找前K个效率非常低最快也要达到O(log2n把整个数组都添加到优先级队列中依次出队堆顶元素用前K个元素建大堆堆顶是当前K个元素中最大的。遍历剩余N-K个元素若元素堆顶替换堆顶并向下调整保持大堆。原理若后续元素比原来的堆顶小说明堆顶元素一定不是第K个小的数则替换堆顶。最终堆中元素即为前K个最小元素。OJ 最小K个数思路2publicint[]smallestK(int[]arr,intk){int[]retnewint[k];PriorityQueueIntegerpriorityQueuenewPriorityQueue();for(inti0;iarr.length;i){priorityQueue.offer(arr[i]);}for(inti0;ik;i){ret[i]priorityQueue.poll();}returnret;}思路3注意要考虑K0的情况否则会报IllegalArgumentException非法参数异常classSolution{publicint[]smallestK(int[]arr,intk){int[]retnewint[k];if(k0)returnret;PriorityQueueIntegerpriorityQueuenewPriorityQueue(k,newPriorityComparator());for(inti0;ik;i){priorityQueue.offer(arr[i]);}for(intik;iarr.length;i){if(priorityQueue.peek()arr[i]){priorityQueue.poll();priorityQueue.offer(arr[i]);}}for(inti0;ik;i){ret[i]priorityQueue.poll();}returnret;}}publicclassPriorityComparatorimplementsComparatorInteger{Overridepublicintcompare(Integero1,Integero2){returno2-o1;}}
