• 数据结构之【堆】（Heap）

    目录

    1. 优先级队列（Priority Queue）

    2.堆的概念

    3.堆的存储方式

    4.堆的创建

    5.用堆模拟实现优先级队列

     6.PriorityQueue常用接口介绍

    6.1 PriorityQueue的特点

    6.2 PriorityQueue几种常见的构造方式

    7.top-k问题

    8.堆排序

    本篇主要内容总结

    （1）优先级队列底层是堆来实现的

    （2）堆的本质是完全二叉树  ，堆有大根堆和小根堆

    （3）大根堆：根节点最大的堆； 小根堆：根节点最小的堆

    （4）堆的创建实现：大根堆为例

    大根堆创建：孩子结点和根节点比较交换，核心思想：向下调整   时间复杂度O(n)

    堆的插入：插入到最后一个位置，和根结点交换，核心思想：向上调整

    堆的删除：只能删除堆顶，然后重新向下调整组成新的大根堆

    插入和删除时间复杂度O（log n）

    （4）priorityQueue建堆是小根堆，如果要建立大根堆就要写比较器

    （5）priorityQueue添加元素，要写明比较的类型才能添加

    （6）top-K问题：前K个最大的元素建小根堆；前K个最小的元素建大根堆

    第K个最大元素建小根堆 拿栈顶；    第K个最小元素建大根堆 拿栈顶

    （7）堆排序：升序：大根堆    降序：小根堆

    核心思想：堆元素的删除

     

    在说堆的概念之前，先说一下堆的常用方法，从这个方向来写这篇文章

    堆的常用方法有

    （1）用来构建优先级队列

    （2）支持堆排序（大堆或小堆）

    （3）top-k问题

    1. 优先级队列（Priority Queue）

    优先级队列 ：是不同于先进先出队列的另一种队列。每次从队列中取出的是具有最高优先权的元素。

    优先级队列相对于普通队列应该提供两个最基本的操作，

    （1）返回最高优先级对象（2）添加新的对象

    在JDk1.8中的优先级队列底层使用了堆

    2.堆的概念

    简单的说 ，堆这种数据结构本质上就是一个完全二叉树

    并且堆中某个结点的值总是不大于或不小于其父结点的值

    小堆：根节点最小的堆，满足Ki <= K2i+1 且 Ki <= K2i+2 

    大堆：根节点最大的堆,   满足Ki >= K2i+1 且 Ki >= K2i+2 

    3.堆的存储方式

    堆是一颗完全二叉树，所以按照层序来看，可以采用顺序数组的存储方式

    但是非完全二叉树就不适用于顺序存储了，这是因为非完全二叉树如果有空结点，那顺序存储也要存储这个空节点，这就造成空间上的浪费

    i表示孩子结点，父亲结点（i-1）/ 2

    i表示根节点 ，左孩子 2 * i + 1    右孩子   2 * i + 2

    4.堆的创建

    5.用堆模拟实现优先级队列

    按照大根堆来创建

    先写一个数组，按顺序存储的方式

    1.     public int[] elem;
    2.     public int userSize;//当前堆中有效的元素数据个数
    3.  
    4.     public MyHeap() {
    5.         this.elem = new int[10];
    6.         this.userSize = 0;
    7.     }
    8.  
    9.     public void initArray(int[] array) {
    10.         elem = Arrays.copyOf(array,array.length);
    11.         userSize = elem.length;
    12.     }

    (1) 创建堆

    先写一个向下调整的方法

    1.   /**
    2.      * @param parent: 每颗子树的根节点下标
    3.      * @param len:每颗子树的结束位置
    4.      * @description 向下调整
    5.      */
    6.     private void shiftDown(int parent,int len) {
    7.         int child = 2*parent+1;//左孩子
    8.         //必须要有左孩子
    9.         while(child < len) {
    10.             //如果一定有右孩子。那就判断 左孩子和右孩子大小，谁大保存谁
    11.             if(child + 1 < userSize && elem[child] < elem[child+1]) {
    12.                 child++;
    13.             }
    14.             //交换 比较孩子和根大小交换 然后根节点往下走继续必须
    15.             if (elem[child] > elem[parent]) {
    16.                 swap(elem,child,parent);
    17.                 parent = child;
    18.                 child = 2*parent+1;
    19.             }else {
    20.                 break;
    21.             }
    22.         }
    23.     }

    再写一个交换根和孩子的方法

    1.     //交换  比较孩子和根大小交换
    2.     private void swap(int[] array, int i, int j) {
    3.         int tmp = array[i];
    4.         array[i] = array[j];
    5.         array[j] = tmp;
    6.     }

    然后通过循环每个结点，向下调整，然后创建好这棵树

    1.     /**
    2.      *建堆：大根堆
    3.      *时间复杂度O(n)
    4.      */
    5.     public void createHeap() {
    6.         for (int parent = (userSize-1-1)/2; parent >= 0 ; parent--) {
    7.             shiftDown(parent,userSize);
    8.         }
    9.     }

    分析一下建堆的时间复杂度O(n)

     （2）堆的插入

    先写一个方法来判断空间满不满

    1.     public boolean isFull() {
    2.         return userSize == elem.length;
    3.     }

    再写一个向上调整

    1.  //向上调整
    2.     private void shiftUp(int child) {
    3.         int parent = (child - 1) / 2;
    4.         while(child > 0) {
    5.             if(elem[child] > elem[parent]) {
    6.                 swap(elem,child,parent);
    7.                 child = parent;
    8.                 parent = (child - 1) / 2;
    9.             }else {
    10.                 break;
    11.             }
    12.         }
    13.     }

     最后再写堆的插入，如果空间满了就扩容，然后再向上调整，变成新的大根堆

    1.     //堆的插入
    2.     public void offer(int x) {
    3.         if (isFull()) {
    4.             elem = Arrays.copyOf(elem,2*elem.length);
    5.         }
    6.         this.elem[userSize] = x;
    7.         userSize++;
    8.         shiftUp(userSize-1);
    9.     }

     （3）堆的删除（优先级队列删除，只能删除堆顶的元素）

    再删除前，先要看堆是不是空的

    1.     public boolean isEmply() {
    2.         return userSize == 0;
    3.     }

    然后再删除堆顶元素

    1.   //堆的删除  只能删除堆顶元素
    2.     public int poll() {
    3.         if (isFull()) {
    4.             return -1;
    5.         }
    6.         int old = elem[0];
    7.         //1.交换
    8.         swap(elem,0,userSize-1);
    9.         //2.有效元素个数-1
    10.         userSize--;
    11.         //3.栈顶元素向下调整
    12.         shiftDown(0,userSize);
    13.         return old;
    14.     }

    看几个选择题把 

    1.已知小根堆为8,15,10,21,34,16,12，删除关键字8之后需重建堆，在此过程中，关键字之间的比较次数是     (C)
    A: 1 B: 2 C: 3 D: 4

    2.最小堆[0,3,2,5,7,4,6,8],在删除堆顶元素0之后，其结果是    ()

    A: [3 ， 2 ， 5 ， 7 ， 4 ， 6 ， 8] B: [2 ， 3 ， 5 ， 7 ， 4 ， 6 ， 8]
    C: [2 ， 3 ， 4 ， 5 ， 7 ， 8 ， 6] D: [2 ， 3 ， 4 ， 5 ， 6 ， 7 ， 8]

     6.PriorityQueue常用接口介绍

    6.1 PriorityQueue的特点

    （1）首先最重要的先明白priorityQueue建堆是小根堆

    1.     public static void main(String[] args) {
    2.         //默认是小根堆
    3.         PriorityQueue priorityQueue = new PriorityQueue<>();
    4.         priorityQueue.offer(45);
    5.         priorityQueue.offer(12);
    6.         priorityQueue.offer(55);
    7.         priorityQueue.offer(66);
    8.         System.out.println(priorityQueue.peek());
    9.     }

    可以看到这里打印的是12所以是priorityQueue是小根堆

    如果要建堆为大根堆，那就要写比较器Comparator了 

    1.     public static void main(String[] args) {
    2.        PriorityQueue priorityQueue = new PriorityQueue<>(new Comparator() {
    3.            @Override
    4.            public int compare(Integer o1, Integer o2) {
    5.                return o2-o1;
    6.            }
    7.        });
    8.     }

     

    （2） 在priorityQueue使用offer添加元素时，一定要明确比较的规则，然后再添加

    如果是直接这样比较的话，offer不知道以什么规则比较然后添加，就会报错。 

    1.     public static void main(String[] args) {
    2.         PriorityQueue priorityQueue = new PriorityQueue<>();
    3.         priorityQueue.offer(new Fruit() );
    4.         priorityQueue.offer(new Fruit() );
    5.     }

    所以这里必须告诉offer以什么方式比较添加，

    比如说这里实现comparable接口

    1. class Fruit implements Comparable{
    2.     public int age;
    3.     //必须告诉priorityQueue.offer 以什么方式比较添加元素
    4.     @Override
    5.     public int compareTo(Fruit o) {
    6.         return this.age - o.age;
    7.     }
    8. }

    （3）不能插入null对象，否则会抛出NullPointerException异常

    （4）可以插入任意多个元素，会自动扩容，没有容量限制

     

     （5）插入和删除元素的时间复杂度为O(log n),建栈的时间复杂度O（n）

    6.2 PriorityQueue几种常见的构造方式

    （1）PriorityQueue()   初始默认容量为11

    （2）PriorityQueue(int initialCapacity)

    （3）PriorityQueue(Collection c)

     

    （4）PriorityQueue(int initialCapacity, Collection comparator

    7.top-k问题

    适用情况，在数据量比较大时，求数据集合中前K个最大的元素或者最小的元素

    比如说求很多个元素的前k个最大的元素 

    思路1：

    （1）将这些元素，全部放进大根堆中，堆顶的元素就是最大的值

    （2）然后出k次，就能得到前k个最大的值，并且每出一次都会进行向下调整，变成新的大根堆

    1.  public static void topK1(int[] array, int k) {
    2.         PriorityQueue maxPQ = new PriorityQueue<>(new Comparator() {
    3.             @Override
    4.             public int compare(Integer o1, Integer o2) {
    5.                 return o2-o1;
    6.             }
    7.         });
    8.  
    9.         for (int i = 0; i < array.length; i++) {
    10.             maxPQ.offer(array[i]);
    11.         }
    12.         for (int i = 0; i < k; i++) {
    13.             int val = maxPQ.poll();
    14.             System.out.println(val);
    15.         }
    16.         System.out.println();
    17.     }
    18.     public static void main(String[] args) {
    19.         int[] array = {16,15,22,155,89,12,45};
    20.         topK1(array,3);
    21.     }

     

     缺点：数字有多少，这个堆就有多大，时间复杂度是O(n*log n)

     思路2：

    （1）求前K个最大的元素，建立大小为K的小根堆

    （2）然后用剩下的集合里面的元素轮流和堆顶元素比较，如果剩下集合里面的元素比堆顶的元素大，那就替换掉堆顶的元素

    （3）然后向下调整，变成新的小根堆，此时这个堆中的元素就是前K个最大元素

    1. 那如果要求前K个最小的元素，如何做
    差不多和前面一样的方法，不同的是
    （1）求前K个最小的元素，要建立大根堆
    （2）比较的时候谁小，就把小的放在堆顶

     力扣链接：   面试题 17.14. 最小K个数 - 力扣（LeetCode）

    1. class Solution {
    2.     public int[] smallestK(int[] arr, int k) {
    3.        int[] ret = new int[k];
    4.         if(k == 0) return ret;
    5.         PriorityQueue maxPQ = new PriorityQueue<>(k,new Comparator() {
    6.             @Override
    7.             public int compare(Integer o1, Integer o2) {
    8.                 return o2-o1;
    9.             }
    10.         });
    11.  
    12.         for (int i = 0; i < arr.length; i++) {
    13.             if(maxPQ.size() < k) {
    14.                 maxPQ.offer(arr[i]);
    15.             }else {
    16.                 //获取到堆顶元素
    17.                 int top = maxPQ.peek();
    18.                 //找前k个最小的
    19.                 if(arr[i] < top) {
    20.                     maxPQ.poll();
    21.                     maxPQ.offer(arr[i]);
    22.                 }
    23.             }
    24.         }
    25.         for (int i = 0; i < k; i++) {
    26.             ret[i] = maxPQ.poll();
    27.         }
    28.         return ret;
    29.     }
    30. }
    2. 那如果要求第K大的元素，或者第K小的元素如何做
    （1）前面求前K个最大的元素时，建立的小根堆，按照规则，到最后栈中全部都是前K个最大的元素，然后栈顶就是所要求得的第K大的元素
    （2）前面求前K个最小的元素时，建立的大根堆，按照规则，到最后栈中全部都是前K个最小的元素，然后栈顶就是所要求得的第K小的元素

    8.堆排序

     如果是将堆排成一个升序的，那就建立大根堆，操作如下

    1.     public void heapSort() {
    2.         int end = userSize -1;
    3.         while(end > 0) {
    4.             swap(elem,0,end);
    5.             shiftDown(0,end);
    6.             end--;
    7.         }
    8.     }

     

    如果是将堆排成一个降序的，那就建立小根堆，操作和上面类似

    一组记录排序码为(5 11 7 2 3 17),则利用堆排序方法建立的初始堆为  (C)
    A: (11 5 7 2 3 17) B: (11 5 7 2 17 3) C: (17 11 7 2 3 5)
    D: (17 11 7 5 3 2) E: (17 7 11 3 5 2) F: (17 7 11 3 2 5)

     

     

  • 相关阅读:
    Mp3文件标签信息读取和写入(Kotlin)
    Linux生成UUID的算法方式（序列号C/C++代码实现）
    Fiddler的下载安装及使用（包括在测试中的使用）
    机器学习笔记 十六：基于Boruta算法的随机森林（RF）特征重要性评估
    强化学习领域值得关注的国际顶级会议
    基于Python Scrapy爬虫改进KNN算法的网站分类系统
    Revit中柱与梁不能连接问题和“柱断墙梁”功能介绍
    【记一次vsan数据救援的经历】
    HCIP第十八天笔记
    微服务系列之网关(二) konga配置操作
  • 原文地址：https://blog.csdn.net/m0_58761900/article/details/125804593