锐客网

  1. 首页 > 睿知 > it技术 > >

java-堆（优先级队列）

堆：使用数组保存二叉树结构，方式即将二叉树用层序遍历方式放入数组中。一般只适合表示完全二叉树，因为非完全二叉树会有空间的浪费。这种方式的主要用法就是堆的表示。
一：堆的概念
1，堆逻辑上是一棵完全二叉树。
2，堆物理上是保存在数组中。
3，满足任意结点的值都大于其子树中结点的值，叫做大堆，或者大根堆，或者最大堆。
4， 反之，则是小堆，或者小根堆，或者最小堆。
5， 堆的基本作用是，快速找集合中的最值。
java-堆（优先级队列）
文章图片

二：下标关系：（操作堆过程中常用逻辑关系）
已知双亲(parent)的下标，则：
左孩子(left)下标 = 2 * parent + 1; 右孩子(right)下标 = 2 * parent + 2;
已知孩子（不区分左右）(child)下标，则：
双亲(parent)下标 = (child - 1) / 2;
三：堆的操作：
（1）向下调整（将一个不是满足堆的数组调整为一个满足大堆或者小堆特点的数组）前提：左右子树必须已经是一个堆，才能调整。以建小堆为例，当建大堆时只需将判断条件换为array[index] >= array[max]即可。
index 如果已经是叶子结点，则整个调整过程结束
1. 判断 index 位置有没有孩子。
2. 因为堆是完全二叉树，没有左孩子就一定没有右孩子，所以判断是否有左孩子
3. 因为堆的存储结构是数组，所以判断是否有左孩子即判断左孩子下标是否越界，即 left >= size 越界
4. 确定 left 或 right，谁是 index 的最小孩子 min
5. 如果右孩子不存在，则 min = left
6. 否则，比较 array[left] 和 array[right] 值得大小，选择小的为 min
7. 比较 array[index] 的值 和 array[min] 的值，如果 array[index] <= array[min]，则满足堆的性质，调整结束
8. 否则，交换 array[index] 和 array[min] 的值
9. 然后因为 min 位置的堆的性质可能被破坏，所以把 min 视作 index，向下重复以上过程.
（2）建堆：数组逻辑上可以看做一颗完全二叉树，但是还不是一个堆，通过算法，把它构建成一个堆。当根节点左右子树不是堆，从倒数的第一个非叶子节点的子树开始调整，一直调整到根节点的树，就可以调整成堆。
1，从数组最后一个元素的父节点开始向下调整（调用上述向下调整方法），最后一个元素的父节点下标为（array.length-2)/2。
2，直到调整至下标为0时，就可以调整为堆。
四：堆的应用（优先级队列）
数据结构应该提供两个最基本的操作，一个是返回最高优先级对象，一个是添加新的对象。这种数据结构就是优先级队列(Priority Queue)。优先级队列的实现方式有很多，但最常见的是使用堆来实现。
（1）入队列（以大堆为例）
1. 首先按尾插方式放入数组
2. 比较其和其双亲的值的大小，如果双亲的值大，则满足堆的性质，插入结束
3. 否则，交换其和双亲位置的值，重新进行 2、3 步骤
4. 直到根结点 。
（2）出队列（优先级最高）
为了防止破坏堆的结构，删除时并不是直接将堆顶元素删除，而是用数组的最后一个元素替换堆顶元素，然后通过向下调整方式重新调整成堆。
五：优先级队列（TopK问题）
1，求一组数据中，K个最小数：遍历整个数组，在遍历前K个数时建立大堆，当遍历第k+1个数时开始与堆顶元素进行比较，若小于堆顶元素则交换，否则继续下一个，直至整个数组都被遍历完。
2，求一组数据中，K个最大数：遍历整个数组，在遍历前K个数时建立小堆，当遍历第k+1个数时开始与堆顶元素进行比较，若大于堆顶元素则交换，否则继续下一个，直至整个数组都被遍历完。
github:https://github.com/bobobo00/TestHeap.git
https://github.com/bobobo00/MypriorityQueuen.git
https://github.com/bobobo00/TopK.git










【java-堆（优先级队列）】

    推荐阅读


    上一篇：没有了

    下一篇：rabbitmq|rabbitmq-server-3.8.16 安装部署