堆优先级队列堆优先级队列堆传统队列先进先出FIFO的数据结构优先级队列在某些场景下操作的数据带有优先级出队时需要优先级高的元素先出队基本操作返回最高优先级对象添加新的对象优先级队列的模拟实现PriorityQueue 底层使用了堆Heap这种数据结构而堆是在完全二叉树的基础上进行调整得到的堆的概念设关键码集合K{k0,k1,k2,…,kn−1}K \{k_0, k_1, k_2, \dots, k_{n-1}\}K{k0​,k1​,k2​,…,kn−1​}将其所有元素按完全二叉树的顺序存储方式存放在一维数组中并满足小根堆最小堆Ki≤K2i1K_i \le K_{2i1}Ki​≤K2i1​且Ki≤K2i2K_i \le K_{2i2}Ki​≤K2i2​根节点最小)大根堆最大堆Ki≥K2i1K_i \ge K_{2i1}Ki​≥K2i1​且Ki≥K2i2K_i \ge K_{2i2}Ki​≥K2i2​根节点最大堆的性质堆中某个节点的值总是不大于或不小于其父节点的值堆总是一棵完全二叉树堆的存储方式堆采用层序遍历规则的顺序存储数组完全二叉树适合顺序存储空间连续且无额外空缺一般二叉树不适合顺序存储为了还原树形结构必须在数组中保留空节点位置导致空间利用率低下标与父子节点对应关系假设节点下标为iii若i0i 0i0表示根节点否则其父节点下标为(i−1)/2(i - 1) / 2(i−1)/2若2i1size2i 1 \text{size}2i1size左孩子下标为2i12i 12i1否则无左孩子若2i2size2i 2 \text{size}2i2size右孩子下标为2i22i 22i2否则无右孩子堆的创建与核心操作堆的向下调整Shift Down前提是待调整节点的左右子树必须已经满足堆的性质调整步骤小堆为例parent 标记当前需要调整的节点child 2 * parent 1 标记左孩子当 child size 时循环若右孩子存在child 1 size且右孩子小于左孩子则 child找到较小的孩子比较 parent 与较小孩子 child若 array[parent] array[child]说明已满足堆性质调整结束退出循环否则交换 parent 与 child 的值然后令 parent childchild 2 * parent 1继续向下调整publicvoidshiftDown(int[]array,intparent){intchild2*parent1;// 先标记左孩子intsizearray.length;while(childsize){// 如果右孩子存在找到左右孩子中较小者if(child1sizearray[child1]array[child]){child1;}// 如果双亲比最小的孩子还小已满足堆特性if(array[parent]array[child]){break;}else{// 交换inttarray[parent];array[parent]array[child];array[child]t;// 顺着子树继续向下调整parentchild;childparent*21;}}}时间复杂度最坏情况下从根节点一路比较到叶子节点移动次数为完全二叉树的高度即O(log⁡N)O(\log N)O(logN)堆的创建对于任意无序序列从倒数第一个非叶子节点下标为 (array.length - 2) / 2开始依次向前直到根节点下标 0对每个节点执行向下调整publicstaticvoidcreateHeap(int[]array){// 找倒数第一个非叶子节点往前依次进行向下调整introot(array.length-2)/2;for(;root0;root--){shiftDown(array,root);}}堆的插入Shift Up 向上调整将新元素插入到数组末尾空间不足时先扩容将该节点顺着双亲链路向上调整直到满足堆的性质publicvoidshiftUp(intchild){intparent(child-1)/2;// 找到双亲节点while(child0){// 以小根堆为例若双亲小于等于孩子已满足堆性质if(array[parent]array[child]){break;}else{// 交换双亲与孩子inttarray[parent];array[parent]array[child];array[child]t;// 向上移动childparent;parent(child-1)/2;}}}堆的删除默认删除的是堆顶元素步骤将堆顶元素与堆中最后一个元素交换有效元素个数减 1size–对堆顶元素执行向下调整shiftDown(0)publicstaticintremove(int[]arry,intsize){if(size0){thrownewRuntimeException(堆已空);}arry[0]arry[size-1];size--;shiftDown(arry,size,0);returnsize;}优先级队列模拟实现代码publicclassMyPriorityQueue{privateint[]arraynewint[100];privateintsize0;// 入队/插入publicvoidoffer(inte){array[size]e;shiftUp(size-1);}// 出队/删除优先级最高元素publicintpoll(){intoldValuearray[0];array[0]array[--size];shiftDown(0);returnoldValue;}// 获取优先级最高元素publicintpeek(){returnarray[0];}}堆的应用Top-K 问题问题描述求海量数据集合中前KKK个最大或最小的元素数据量巨大无法一次性全载入内存排序解法对元素进行排序找出前KKK个最大或最小的元素冒泡排序只要KKK次就可以找出KKK个最大或最小的元素最优堆解法思路求前KKK个最大的元素取前KKK个元素建立小根堆遍历剩余N−KN-KN−K个元素若当前元素比小根堆堆顶大则替换堆顶并向下调整最终堆内保留的KKK个元素就是前KKK个最大值求前KKK个最小的元素取前KKK个元素建立大根堆遍历剩余N−KN-KN−K个元素若当前元素比大根堆堆顶小则替换堆顶并向下调整最终堆内保留的KKK个元素就是前KKK个最小值例 arr [ 1,3,5,7,2,4,6,8 ] K 4 数组中最小的 k 个数大根堆初始化大根堆创建一个容量为kkk的优先队列遍历数组更新堆当堆中元素不足kkk个时直接将当前数字入堆当堆满已有kkk个元素时将当前元素与堆顶即当前候选集中最大的数进行比较若当前元素小于堆顶元素说明堆顶元素不可能是全局最小的前kkk个数之一于是弹出堆顶将当前元素加入堆中若当前元素大于或等于堆顶元素则直接跳过导出结果遍历结束后堆中保留的正是数组中最小的kkk个元素。依次弹出堆中所有元素存入结果数组 res 并返回staticclassMyMaxComparatorimplementsComparatorInteger{Overridepublicintcompare(Integera,Integerb){returnb-a;//大根堆大元素优先堆顶}}publicint[]smallestK(int[]arr,intk){if(k0)returnnewint[0];PriorityQueueIntegerpqnewPriorityQueue(newMyMaxComparator());for(inti0;iarr.length;i){if(pq.size()k){pq.offer(arr[i]);}else{if(arr[i]pq.peek()){pq.poll();pq.offer(arr[i]);}}}int[]resnewint[k];for(inti0;ik;i){res[i]pq.poll();}returnres;}