Heap —— Priority Queue 【堆 / 优先队列】

转x33g5p2x  于2022-02-07 转载在 其他  
字(9.3k)|赞(0)|评价(0)|浏览(357)

前言 - 为堆的学习做准备

二叉树的顺序存储

前面所讲的二叉树，什么孩子表示法呀，还有 孩子双亲表示法啊，都是链式存储。
而现在讲的是：顺序存储一棵二叉树。

存储方式

使用数组保存二叉树结构，方式即将二叉树用层序遍历的方式放入数组中。
一般只适合表示完全二叉树，因为 非完全二叉树会有空间的浪费。【也就是说：如果使用顺序存储来存储一棵二叉树，那么，最好是完全二叉树，这样就不会有太多的空间被浪费】
这种方式的主要用法就是堆的表示。

下标关系

已知双亲（parent）的下标，则：
左孩子（left）下标 = 2 * parent + 1；
右孩子（right）下标 = 2 * parent + 2；
已知孩子（不区分左右）（child）下标，则：
双亲（parent）下标 = （child - 1）/ 2；
就是我在 二叉树那篇 文章 所讲的 二叉树的第五个性质

堆 【heap】

概念

1、堆在逻辑上是一棵完全二叉树
2、堆在物理上是保存在数组中。
3、满足任意节点的值 都大于 自身所在树中根结点的值，叫做小堆，或者小根堆，或者是最小堆。【每棵二叉树的根结点 都小于 左右孩子结点 - 小堆 / 小根堆 / 最小堆】

  1. 满足任意节点的值 都小于 自身所在树中根结点的值，叫做大堆，或者大根堆，或者是最大堆。【每棵二叉树的根结点 都大于 左右孩子结点 -大堆 / 大根堆 / 最大堆】

  1. 堆的基本作用是，快速找集合中的最值
    无论是 大根堆还是小根堆， 它们的 最值【最大值 和 最小值】都处于 二叉树的 根结点处。要想获得 最值，直接 peek 方法，就能获得 树 的 根结点值 / 最值。
    这也是为什么说： 堆 是 优先级队列。
    所谓优先级队列：存入一个数据，是按照某种特殊规定来存储的。
    而这种规则就是刚刚讲的 大小根堆的特性。将最值放在最容易获取的位置。
    也就是说： 优先级队列 其 底层 是 一棵 完全二叉树 / 堆。

操作-向下调整

前提：左右子树必须已经是一个 堆 / 逻辑上是一棵完全二叉树。

实战 - 将一组 记录完全二叉树数据 的 数组 转换成 大根堆。

向下调整 - 结论
  1. 调整是从最后一棵子树触发的
    2、每棵子树的调整都是向下调整。
    3、之所以称为向下调整，是因为 在 调整的过程中，根结点 是 跟 左右子树 进行交换，那么根结点是不是就下来了。所以才称为 向下调整【根结点的值，向下移动 / 与左右子树的值进行交换】。

问题

1、如何找到最后一棵子树

因为 堆 在 逻辑 上 是 一 棵 完全二叉树，物理上 其数据 是由数组保存的。
两者的共同点：完全二叉树的编号 与 数组下标 一致。
也就是说：我们只要获取数组的长度 len，那么 len -1 ，不就是 最后一棵子树的下标。
此时，我们是不是得到了一个 孩子结点 的 下标【child】？
根据 下标关系,我们就可以通过 孩子结点的下标，来获取 双亲节点 / 父 节点 的下标
parent == （child - 1）/ 2 》》parent == （（len - 1） - 1）/ 2

2、如何将所有树的调整成大根堆 【遍历 每棵 树的 根结点，因为向下调整需要知道根结点的】

很简单，既然我们通过 数组的长度，间接获取到了最后一棵子树的根结点【parent】，那么，我们直接 parent - - ，就可以获取所有子树，包括整棵树的根结点。

通过 双亲节点 parent 和 下标关系，我们就可以获取 其 左右子树的下标。
【 左子树：parent * 2 + 1；右子树：parent * 2 + 2】

每棵树的调整结束的位置，如何判定？

得出结论：其实每棵树的调整结束位置 都是一样的 ：不能超过 数组长度。【细品】

如何构造一个 向下调整的函数 - 重点
  1. // 向下调整
  2.     public void shiftDown(int parent,int len){
  3.         int child = parent * 2 + 1;// 左孩子
  4.         // 能进入该循环，说明 这个 parent 只少有一个孩子。
  5.         while(child < len){
  6.             // 获取 左右孩子的最大值
  7.             if(child+1 < len &&this.elements[child] < this.elements[child+1]){
  8.                 child++;
  9.             }
  10.             // 判断 孩子最大值 是否 比  双亲节点 val 值 大
  11.             // 如果大，就需要进行交换
  12.             if(this.elements[child] > this.elements[parent]){
  13.                 int tmp = elements[child];
  14.                 elements[child] = elements[parent];
  15.                 elements[parent] = tmp;
  16.                 
  17.                 // 见附图
  18.                 parent = child;
  19.                 child = parent * 2 + 1;
  20.             }else{
  21.                 break;
  22.             }
  23.         }
  24.     }
附图

模拟实现 堆 - 程序框架

  1. import java.util.Arrays;
  3. public class Heap {
  4.     public int[] elements;// 底层数组
  5.     public int usedSize;// 有效元素个数
  6.     // 构造方法
  7.     public Heap(int[] elements){
  8.         // 数组初始化容量
  9.         this.elements = new int[10];
  10.     }
  11.      // 创建堆，获取 输入数组 的 数据
  12.     public void creationHeap(int[] array){
  13.         this.usedSize += array.length;
  14.         if(isFull()){
  15.             this.elements = Arrays.copyOf(this.elements,this.elements.length*2);
  16.         }
  17.         this.elements = Arrays.copyOf(array,array.length);
  19.         for(int parent = (this.usedSize -1 - 1)/2 ;parent >= 0;parent--){
  20.             // 向下调整
  21.             shiftDown(parent,this.usedSize);
  22.         }
  23.     }
  24.     // 向下调整
  25.     public void shiftDown(int parent,int len){
  26.         int child = parent * 2 + 1;// 左孩子
  27.         // 能进入该循环，说明 这个 parent 只少有一个孩子。
  28.         while(child < len){
  29.             // 获取 左右孩子的最大值
  30.             if(child+1 < len &&this.elements[child] < this.elements[child+1]){
  31.                 child++;
  32.             }
  33.             // 判断 孩子最大值 是否 比  双亲节点 val 值 大
  34.             // 如果大，就需要进行交换
  35.             if(this.elements[child] > this.elements[parent]){
  36.                 int tmp = elements[child];
  37.                 elements[child] = elements[parent];
  38.                 elements[parent] = tmp;
  40.                 // 见附图
  41.                 parent = child;
  42.                 child = parent * 2 + 1;
  43.             }else{
  44.                 break;
  45.             }
  46.         }
  47.     }
  48. }

模拟实现 堆 的 时间复杂度

堆的应用 - 优先级队列

概念

在很多应用中，我们通常需要按照优先级情况 对待处理对象 进行处理，比如说首先处理优先级最高的对象，然后处理 次高的对象。
举个最简单的例子就是：

直接调用 优先级队列，系统默认生成是 小根堆。

下面我们就来实践。首先创建一个 优先级队列 / 堆。

按住 Ctrl ，左键点击框选部分，进入该类的内部。
按一下 alt + 7，就会弹出功能菜单，如下图所示：【现在先关注队列的功能】

利用 offer 来给 优先级队列 / 堆 提供数据。再来通过 peek 方法 来观察 队头元素 / 堆的根结点，如果为 最小值，那么说 优先级队列默认是小根堆，反之，就是大根堆。

所谓优先级队列：不管是出队，还是入队。都得保证当前是大根堆 或者 小根堆。

优先级队列 - 入队 和 出队 过程

大根堆情况 （向上调整）

1、 首先按尾插方式放入数组
2、 比较其 和 其双亲的值 的 大小，如果双亲的值大，则满足堆的性质，插入结束
3、 否则，交换其和双亲位置的值，重新进行 2、3 步骤
4.、直到根结点

我们将其过程称为 向上调整。
向上调整：只需要一个参数【需要调整的 child 下标】

模拟实现 堆 - offer 功能 - 入队
  1. // 入队操作
  2.     public void offer(int val){
  3.         if(isFull()){
  4.             // 扩容
  5.             this.elements = Arrays.copyOf(this.elements,this.elements.length * 2);
  6.         }
  7.         elements[usedSize++] = val;
  8.         //usedSize++;
  9.         shiftUp(usedSize-1);// 有效元素个数 是 usedSize,最后一个元素的下标是 usedSize -1
  10.     }
  11.     private void shiftUp(int child){
  12.         int parent = (child - 1)/2;
  13.         while(child > 0){
  14.             if(this.elements[child] > this.elements[parent]){
  15.                 int tmp = this.elements[child];
  16.                 this.elements[child] = this.elements[parent];
  17.                 this.elements[parent] = tmp;
  18.                 child = parent;
  19.                 parent = (child - 1) / 2;
  20.             }else{
  21.                 break;
  22.             }
  23.         }
  24.     }
  25.     public boolean isFull(){
  26.         return this.usedSize >= this.elements.length;
  27.     }

模拟实现 堆 - poll 功能 - 出队
分析

代码如下
  1. // 出队操作
  2.     public int poll(){
  3.         if(isEmpty()){
  4.             throw new RuntimeException("优先级队列为空！");
  5.         }
  6.         int tmp = this.elements[0];
  7.         this.elements[0] = this.elements[this.usedSize -1];
  8.         this.elements[this.usedSize - 1] = tmp;
  9.         this.usedSize--;
  10.         shiftDown(0,usedSize);
  11.         return tmp;
  12.     }
  14.     // 判断队列 空不空
  15.     public boolean isEmpty(){
  16.         return this.usedSize == 0;
  17.     }

模拟实现 堆 - peek 功能 - 返回队头元素
  1. // 判断队列 空不空
  2.     public boolean isEmpty(){
  3.         return this.usedSize == 0;
  4.     }
  5.     public int peek(){
  6.         if(isEmpty()){
  7.             throw new RuntimeException("优先级队列为空！");
  8.         }
  9.         return this.elements[0];
  10.     }

模拟实现 堆 【总程序】

  1. import java.util.Arrays;
  3. public class Heap {
  4.     public int[] elements;// 底层数组
  5.     public int usedSize;// 有效元素个数
  6.     // 构造方法
  7.     public Heap(){
  8.         // 数组初始化容量
  9.         this.elements = new int[10];
  10.     }
  11.      // 创建堆，获取 输入数组 的 数据
  12.     public void creationHeap(int[] array){
  13.         this.usedSize += array.length;
  14.         if(isFull()){
  15.             this.elements = Arrays.copyOf(this.elements,this.elements.length*2);
  16.         }
  17.         this.elements = Arrays.copyOf(array,array.length);
  19.         for(int parent = (this.usedSize -1 - 1)/2 ;parent >= 0;parent--){
  20.             // 向下调整
  21.             shiftDown(parent,this.usedSize);
  22.         }
  23.     }
  24.     // 向下调整
  25.     public void shiftDown(int parent,int len){
  26.         int child = parent * 2 + 1;// 左孩子
  27.         // 能进入该循环，说明 这个 parent 只少有一个孩子。
  28.         while(child < len){
  29.             // 获取 左右孩子的最大值
  30.             if(child+1 < len &&this.elements[child] < this.elements[child+1]){
  31.                 child++;
  32.             }
  33.             // 判断 孩子最大值 是否 比  双亲节点 val 值 大
  34.             // 如果大，就需要进行交换
  35.             if(this.elements[child] > this.elements[parent]){
  36.                 int tmp = elements[child];
  37.                 elements[child] = elements[parent];
  38.                 elements[parent] = tmp;
  40.                 // 见附图
  41.                 parent = child;
  42.                 child = parent * 2 + 1;
  43.             }else{
  44.                 break;
  45.             }
  46.         }
  47.     }
  49.     // 入队操作
  50.     public void offer(int val){
  51.         if(isFull()){
  52.             // 扩容
  53.             this.elements = Arrays.copyOf(this.elements,this.elements.length * 2);
  54.         }
  55.         elements[usedSize++] = val;
  56.         //usedSize++;
  57.         shiftUp(usedSize-1);// 有效元素个数 是 usedSize,最后一个元素的下标是 usedSize -1
  58.     }
  59.     private void shiftUp(int child){
  60.         int parent = (child - 1)/2;
  61.         while(child > 0){
  62.             if(this.elements[child] > this.elements[parent]){
  63.                 int tmp = this.elements[child];
  64.                 this.elements[child] = this.elements[parent];
  65.                 this.elements[parent] = tmp;
  66.                 child = parent;
  67.                 parent = (child - 1) / 2;
  68.             }else{
  69.                 break;
  70.             }
  71.         }
  72.     }
  73.     // 判断队列满没满
  74.     public boolean isFull(){
  75.         return this.usedSize >= this.elements.length;
  76.     }
  78.     // 出队操作
  79.     public int poll(){
  80.         if(isEmpty()){
  81.             throw new RuntimeException("优先级队列为空！");
  82.         }
  83.         int tmp = this.elements[0];
  84.         this.elements[0] = this.elements[this.usedSize -1];
  85.         this.elements[this.usedSize - 1] = tmp;
  86.         this.usedSize--;
  87.         shiftDown(0,usedSize);
  88.         return tmp;
  89.     }
  91.     // 判断队列 空不空
  92.     public boolean isEmpty(){
  93.         return this.usedSize == 0;
  94.     }
  95.     public int peek(){
  96.         if(isEmpty()){
  97.             throw new RuntimeException("优先级队列为空！");
  98.         }
  99.         return this.elements[0];
  100.     }
  102. }

堆的其他应用-TopK 问题

给我们一百万个数据，让你找到前10个最大的元素。
目前来说：我们知道堆排序时间复杂度 最快： log2 N * N；最慢： N

思路一 ：整体排序

对整体进行排序，输出前10个最大的元素。
对整体排序这不是一个非常好的思路！
99%的人都能想出来：直接对底层数组进行排序，输出前10个最大的元素。
这样做，出这题的意义就不大。

思路二 ： 利用堆来实现 【这还不是Topk 问题，这里只是打底】

用堆来解决。
思路：将数据建成大根堆。
假设，建好的大根堆如下图所示：

假设，我们要在这个堆上找到 前三个 最大值，该怎么做？

思路二 ：Topk思路

还是跟思路二一样，去求一组数据的前三个最大值。

总结：

1、如果求前K个最大的元素，要建一个小根堆。
2、如果求 前K个最小的元素，要建一个大根堆。
3、如果是求第k大的元素，建一个小堆，小根堆 堆顶的元素就是第k大的元素。
4、如果是求第k小的元素，建一个大堆，大根堆 堆顶的元素就是第k小的元素。

在做实战题之前，我们需要先学习这篇文章Java 对象 的 比较

模拟topK问题【求一组数据的前k个最小值】，并解决它
  1. import java.util.Arrays;
  2. import java.util.Comparator;
  3. import java.util.PriorityQueue;
  5. public class TopK {
  6.     /*
  7.     * 求数组中的前 k 个 最小元素
  8.     * @param array
  9.     * @param  k
  10.     * @return
  11.     * */
  12.     public static int[] topK(int[] array,int k){
  13.         // 创建一个大小为 k 的 大根堆
  14.         PriorityQueue<Integer> maxHeap = new PriorityQueue<>(k, new Comparator<Integer>() {
  15.             @Override
  16.             public int compare(Integer o1, Integer o2) {
  17.                 return o2 - o1;
  18.             }
  19.         });
  20.         for(int i = 0;i <array.length;i++){
  21.             if(maxHeap.size() < k){
  22.                 maxHeap.offer(array[i]);
  23.             }else{
  24.                 // 从第 k + 1 个元素开始，每个元素都要和 堆顶元素进行比较。
  25.                 // 如果 比 堆顶元素小，则与堆顶元素交换，
  26.                 int top = maxHeap.peek();
  27.                 if(top > array[i]){
  28.                     maxHeap.poll();// 先将堆顶元素弹出，优先级队列会自行调整一下
  29.                     maxHeap.offer(array[i]);// 后面入队也是一样，也会自行调整一下
  30.                 }
  31.             }
  32.         }
  33.         // 此时 maxHeap 堆里，存储的是 前 k  个最小的 值
  34.         // 现在要做的是 将其 转换称是数组，返回
  35.         int[] tmp =  new int[k];
  36.         for(int i = 0;i < k;i++){
  37.             tmp[i] = maxHeap.poll();
  38.         }
  39.         return tmp;
  40.     }
  42.     public static void main(String[] args) {
  43.         int[] array = {18,21,8,10,34,12};
  44.         int[] tmp =topK(array,3);// 求前三个最小值
  45.         System.out.println(Arrays.toString(tmp));
  46.     }
  47. }

实战题 - LeetCode - 373. 查找和最小的 K 对数字

题目分析

给了我们两个升序(元素顺序：从小到大)数组 num1 和 num2，让我们分别从 num1 和 num2 中，各自选取 一个 数据，让其 组成 k 个 两个数之和最小 的 组合。
选取的数可以重复利用。

解题 思维

代码如下
  1. class Solution {
  2.     public List<List<Integer>> kSmallestPairs(int[] nums1, int[] nums2, int k) {
  3.     // 创建 一个大小为 k 的 大根堆
  4.         PriorityQueue<List<Integer>> maxHeap = new PriorityQueue<>(k,new Comparator<List<Integer>>(){
  5.             @Override
  6.             public int compare(List<Integer> o1,List<Integer> o2){
  7.                 return ((o2.get(0) + o2.get(1)) - (o1.get(0) + o1.get(1)));
  8.             }
  9.         }); 
  10.         // 我们不需要将数组 num1 和 num2 遍历完
  11.         // 因为 这两个数组是升序，前k个最小数对，一定是 有 num1 和 num2 前k 个元素 组成的。
  12.         for(int i = 0;i < Math.min(nums1.length,k);i++){
  13.             for(int j = 0;j < Math.min(nums2.length,k);j++){
  14.                   // 先放入 k 个 数对
  15.                 if(maxHeap.size()< k){
  16.                     List<Integer> tmpList = new ArrayList<>();
  17.                     tmpList.add(nums1[i]);
  18.                     tmpList.add(nums2[j]);
  19.                     maxHeap.offer(tmpList);
  20.                 }else{// 从 k +1 个 数对，开始判断
  21.                     int top = maxHeap.peek().get(0) +maxHeap.peek().get(1);
  22.                     if(top >(nums1[i] + nums2[j])){
  23.                         // 弹出
  24.                         maxHeap.poll();
  25.                         List<Integer> tmpList = new ArrayList<>();
  26.                         tmpList.add(nums1[i]);
  27.                         tmpList.add(nums2[j]);
  28.                         
  29.                         // 入队
  30.                         maxHeap.offer(tmpList);
  31.                     }
  32.                 }
  33.             }
  34.         }
  35.         // 为返回值做准备
  36.         List<List<Integer>> result = new ArrayList<>();
  37.         // 循环判断条件，需要加上 一个判断 堆是不是为空
  38.         // 根据示例三：两个数组元素 可能存在 不足以构成 k 个最小数对 的情况
  39.         for(int i = 0; i < k && !maxHeap.isEmpty();i++ ){
  40.             result.add(maxHeap.poll());
  41.         }
  42.         return result;
  43.     }
  44. }

堆排序

总结

1、将数据调整为 大根堆、
2、0 下标 与 最后一个未排序的元素进行交换即可。
3、循环上述两个操作，直至 最后一个未排序的元素 下标为 0.。

实战 - 堆排序

  1. public void heapTraversal(){
  2.         // 最后一个未排序元素的下标
  3.         int last = this.elements.length - 1;
  4.         while(last > 0){
  5.             int tmp = this.elements[0];
  6.             this.elements[0] = this.elements[last];
  7.             this.elements[last] = tmp;
  8.             shiftDown(0,last);
  9.             last--;
  10.         }
  11.     }
  12.         // 向下调整
  13.     public void shiftDown(int parent,int len){
  14.         int child = parent * 2 + 1;// 左孩子
  15.         // 能进入该循环，说明 这个 parent 只少有一个孩子。
  16.         while(child < len){
  17.             // 获取 左右孩子的最大值
  18.             if(child+1 < len &&this.elements[child] < this.elements[child+1]){
  19.                 child++;
  20.             }
  21.             // 判断 孩子最大值 是否 比  双亲节点 val 值 大
  22.             // 如果大，就需要进行交换
  23.             if(this.elements[child] > this.elements[parent]){
  24.                 int tmp = elements[child];
  25.                 elements[child] = elements[parent];
  26.                 elements[parent] = tmp;
  28.                 // 见附图
  29.                 parent = child;
  30.                 child = parent * 2 + 1;
  31.             }else{
  32.                 break;
  33.             }
  34.         }
  35.     }

本文结束

版权说明 : 本文为转载文章, 版权归原作者所有 版权申明

原文链接 : https://blog.csdn.net/DarkAndGrey/article/details/122764801

内容来源于网络，如有侵权，请联系作者删除！

数据结构算法深度优先

相关文章

    查看更多

    热门标签

    更多
    JavaquerypythonNode开发语言requestUtil数据库Table后端算法LoggerMessageElementParser

    最新文章

    更多

    目录

    • 蜀ICP备13028337号-1 大数据知识库 https://www.saoniuhuo.com © All rights reserved
    • 本站内容来源互联网,如果侵犯您的权益请联系我们删除, 联系方式：448109455@qq.com