优先级队列(堆)及其背后的数据结构

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

认识堆前的基本概念：
1、完全二叉树：若二叉树的深度为h，则除第h层外，其他层的结点全部达到最大值，且第h层的所有结点都集中在左子树。

2、满二叉树：满二叉树是一种特殊的的完全二叉树，所有层的结点都是最大值。
3、已知树的其中一个孩子结点下标为i，则它的父亲结点的下标为(i-1)/2
4、已知树的其中一个父亲结点下标为i，则它的孩子结点的下标为i*2+1

一、堆

1.堆的概念

  1. 堆逻辑上是一棵完全二叉树
  2. 堆物理上是保存在数组中
  3. 满足任意结点的值都大于其子树中结点的值，叫做大堆，或者大根堆，或者最大堆；反之，则是小堆，或者小根堆，或者最小堆。当一个堆为大堆时，它的每一棵子树都是大堆。
  4. 堆的基本作用是，快速找集合中的最值

二、堆的基本操作

1.创建堆与向下调整

创建堆只有两种堆可以创建，要不就是大根堆，要不就是小根堆。而要满足大根堆还是小根堆的逻辑，要向下调整的操作才能实现。

要想自己实现堆，堆本身就是一个数组，因此创建一个数组来创建堆。（此处以创建大根堆为例）

创建堆思路：首先i从最后一个父亲结点开始，向下调整为大根堆。当调整完其中每一个堆时，将父亲结点的值移到孩子结点的值，而孩子结点的值设置为2*parent+1。当然，如果孩子结点的值一旦大于整个堆的结点数，则在i-1的结点处去调整堆。每一个子树都是按照相同的情况去调整为大堆。

注意的是，算出一个孩子结点可能是其中一个二叉子树的左节点，当然它也有可能有右节点。因此首先判断它有没有右节点，即child+1<len，并且如果有右节点的话要比较右节点和它的值哪一个大，如果右节点比左节点的值大，则child直接指向右节点，否则不需要调整child。再比较两个孩子结点的数组是否比它们的父亲结点的值大。

当parent的下标指向有以它为根节点深度为3的树时，如果两个孩子结点比较后数值较大的孩子结点与父亲结点比较，若父亲结点的数值更大，则不用继续调整了。

例如：

说明：此处的usedSize为数组的最大下标。

  1. public void creatHeap(int[] array) {
  2.         for (int i = 0; i < array.length; i++) {
  3.             elem[i]=array[i];
  4.             usedSize++;
  5.         }
  6.         for (int i = (array.length-1-1)/2; i >=0 ; i--) {
  7.             adjustDown(i,usedSize);
  8.         }
  9.     }
  10.     //每次调整后的结束位置：usedSize
  11.     /*
  12.     向下调整
  13.      */
  14.     public void adjustDown(int parent,int len) {
  15.         int child = parent*2+1;
  16.         while(child<len) {
  17.             if(child+1<len&&elem[child]<elem[child+1]) {
  18.                 child++;
  19.             }
  20.             if(elem[child]>elem[parent]) {
  21.                 int tmp = elem[parent];
  22.                 elem[parent]=elem[child];
  23.                 elem[child]=tmp;
  24.                 parent=child;
  25.                 child=2*parent+1;
  26.             }else {
  27.                 break;
  28.             }
  29.         }
  30.     }

2.创建堆的时间复杂度

有不少初学者认为，创建堆的过程为O(N*log2^N)，N为结点个数。其实不然，创建堆的时间复杂度实际上为O(N)，证明过程如下：

说明：h为整棵树的深度。

因为向下调整是从最后一个父亲结点开始的。因此每一层的结点数乘以它所要调整的堆的高度。还是以上图为例。**下标为0的结点除了它所在的层以外其余的层数都要调整为大根堆，这一层调整的时间复杂度就为2的0次方乘以(h-1)；下标为1和2的结点除了它所在的层和比他低的层外都要调整为大根堆，这一层调整的时间复杂度就为2的1次方乘以(h-2)。**以此类推，最后的时间复杂度为：

式子1：

但我们要对此进行化简，采用数学上的错位相减法。令等式的两边同乘以2，得：

式子2：

让式子2减去式子1：

转化为：

由等比数列的求和公式：

得：

又因为假设该堆有n个结点，深度为h。因为结点数n=2的h次方-1 。因此高度为h=log2为底的（n+1）。将h代入T(n)中得：

因此，创建堆的时间复杂度为T(n)=O(N)。

3.向上调整

向上调整一般适用于优先级队列（已经确定是大堆还是小堆后）中的入队操作后调整堆为大堆还是小堆。
还是以下图为例：我们向上调整是先从最后一个结点的下标作为孩子结点来进行调整，已知孩子结点的下标则能求出父亲结点的下标。若孩子结点的下标小于0，则直接退出循环。当其中一个孩子结点的值小于父亲结点的值，则直接退出循环，（因为已经确定了原本的整个堆为大堆）是因为能够直接确定整个堆已经是一个大堆。

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

4.模拟优先级队列的offer操作

优先级队列的offer操作，是从堆的最后一个位置处插入元素，并且插入后要进行向上调整来确保堆是大堆。

  1. //向上调整
  2.     public void adjustUp(int child) {
  3.         int parent = (child-1)/2;
  4.         while(child>0) {
  5.             if(elem[child]>elem[parent]) {
  6.                 int tmp = elem[parent];
  7.                 elem[parent]=elem[child];
  8.                 elem[child]=elem[parent];
  9.                 child=parent;
  10.                 parent=(child-1)/2;
  11.             }else {
  12.                 break;
  13.             }
  14.         }
  15.     }
  16.       public void offer(int val) {
  17.         if(isFull()) {
  18.             elem = Arrays.copyOf(elem,2*elem.length);
  19.         }
  20.         elem[usedSize++]=val;
  21.         adjustUp(usedSize-1);
  22.       }
  23.       public boolean isFull() {
  24.         return usedSize==elem.length;
  25.     }

5.模拟优先级队列的poll操作

优先级队列中的poll操作是使堆的堆顶元素出队（前提该堆已经是一个大堆）。那么我们可以让堆顶元素与堆的最后一个位置的元素交换，交换后再根据向下调整来调整堆为一个大堆。

代码：

  1. //出最大的元素
  2.     public void pop() {
  3.         if(isEmpty()) {
  4.             return;
  5.         }
  6.         int tmp = elem[0];
  7.         elem[0]=elem[usedSize-1];
  8.         elem[usedSize-1]=tmp;
  9.         usedSize--;
  10.         adjustDown(0,usedSize);
  11.     }
  12.     public boolean isEmpty() {
  13.         return usedSize==0;
  14.     }

三、优先级队列集合的使用

1.优先级队列中的比较规则

Student类：

  1. class Student {
  2.     private String name;
  3.     private int age;
  5.     public Student(String name, int age) {
  6.         this.name = name;
  7.         this.age = age;
  8.     }
  10.     public String getName() {
  11.         return name;
  12.     }
  14.     public void setName(String name) {
  15.         this.name = name;
  16.     }
  18.     public int getAge() {
  19.         return age;
  20.     }
  22.     public void setAge(int age) {
  23.         this.age = age;
  24.     }
  26.     @Override
  27.     public String toString() {
  28.         return "Student{" +
  29.                 "name='" + name + '\'' +
  30.                 ", age=" + age +
  31.                 '}';
  32.     }
  33. }

Test类：

  1. public static void main(String[] args) {
  2.         PriorityQueue<Student> queue = new PriorityQueue<>();
  3.         queue.offer(new Student("bit",18));
  4.         queue.offer(new Student("zjr",8));
  5.         System.out.println(queue);
  6.     }

若直接入队，则编译器会报错。

并且我们在学习Compartor比较器时，对一个类型的数组排序要用Comparable接口或者Comparator接口。不能直接进行比较。

  1. public static void main(String[] args) {
  2.         Student[] students = new Student[2];
  3.         students[0] = new Student("zjr",12);
  4.         students[1] = new Student("bit",89);
  5.         Arrays.sort(students,new NameComparator());
  6.         System.out.println(Arrays.toString(students));
  7.     }

原因是PriorityQueue不知道我们是按照哪个属性去排的序，我们点入PriorityQueue的源码当中，看到了它的其中一个构造方法中能有一个Comparator比较器。

**当然我们也可以用Comparable比较器，但是对类的嵌入性太强，**若重写的compareTo方法只是比较的是它的年龄，则该类只能按照年龄去比较，而不能用姓名去比较了。此处就直接省略了。

那Comparator可以直接创建多个类来实现该接口，可用作多个不同类型的属性的比较。如：

  1. class AgeComparator implements Comparator<Student> {
  3.     @Override
  4.     public int compare(Student o1, Student o2) {
  5.         return o1.getAge()-o2.getAge();
  6.     }
  7. }
  9. class NameComparator implements Comparator<Student> {
  11.     @Override
  12.     public int compare(Student o1, Student o2) {
  13.         return o1.getName().compareTo(o2.getName());
  14.     }
  15. }
  17.     public static void main(String[] args) {
  19.         PriorityQueue<Student> priorityQueue = new PriorityQueue<>(new AgeComparator());
  21.         priorityQueue.offer(new Student("bit",18));
  23.         priorityQueue.offer(new Student("zjr",8));
  25.         System.out.println(priorityQueue);
  27.     }

2.特殊的比较方式

若两个引用进行比较，是地址不同的两个引用。若在该引用的类中重写equals和hashCode方法，并且创建对象的时候创建的属性都是相同的，则调用equals返回的是true。

  1. class Student {
  2.     private String name;
  3.     private int age;
  5.     public Student(String name, int age) {
  6.         this.name = name;
  7.         this.age = age;
  8.     }
  10.     public String getName() {
  11.         return name;
  12.     }
  14.     public void setName(String name) {
  15.         this.name = name;
  16.     }
  18.     public int getAge() {
  19.         return age;
  20.     }
  22.     public void setAge(int age) {
  23.         this.age = age;
  24.     }
  26.     @Override
  27.     public String toString() {
  28.         return "Student{" +
  29.                 "name='" + name + '\'' +
  30.                 ", age=" + age +
  31.                 '}';
  32.     }
  34.     @Override
  35.     public boolean equals(Object o) {
  36.         //是不是两个引用 同时指向一个对象
  37.         if (this == o) return true;
  38.         //如果传进来是一个null
  39.         if (o == null) return false;
  41.         Student student = (Student) o;
  42.         //
  43.         return age == student.age &&
  44.                 Objects.equals(name, student.name);
  45.     }
  46.     //hashmap讲完后
  47.     @Override
  48.     public int hashCode() {
  49.         return Objects.hash(name, age);
  50.     }
  51. }
  52.     public static void main(String[] args) {
  53.         Student student1 = new Student("bit",1);
  54.         Student student2 = new Student("bit",1);
  55.         System.out.println(student1 == student2);//打印结果false
  56.         System.out.println(student1.equals(student2));//打印结果true
  57.     }

3.刨析PriorityQueue中的offer源码

offer中的源码：
我们可以看到，如果不是第一次入队，则要采用向上调整的方式入队。

点入siftUp方法当中，可以看到它会判定使用哪一个比较器。

实际上它们方法内部的操作都是一样的，只不过Comparator根据一些属性的排序的范围更广。参数x为即将要入队的元素。k为队尾的下标，e为父亲结点的元素此时调用compare方法，o1则为即将要插入的元素，o2为父亲结点元素。若compare方法内部返回的是o1-o2，则创建的是小堆。相反，若compare方法内部返回的是o2-o1，则创建的是大堆。

四、有关堆的面试题

1.堆排序（从小到大排）

面试题1：问若一个数组用堆排序要按照从小到大排序，需要如何排序？

答：一个数组根据从小到大排序，要创建大堆来排；一个数组根据从大到小排序，要创建小堆来排。

此处就以创建大堆为例。首先将堆顶的元素和堆中的最后一个元素交换，交换后再向下调整，调整后再与堆的倒数第二个元素进行交换。

代码：

  1. public void HeapSort() {
  2.         int end = usedSize-1;
  3.         while(end>0) {
  4.             int tmp = elem[0];
  5.             elem[0]=elem[end];
  6.             elem[end]=tmp;
  7.             adjustDown(0,end);
  8.             end--;
  9.         }
  10.     }

2.topK问题

面试题2：问如何从100w个数字中取得最小的10数字，打印出来的数字不用排序。

答：若要从N个数字中取得最小的K个数字，则需要创建大小为K的大堆来获取。若压迫从N个数字中取得最大的K个数字，则需要创建大小为K的小堆来获取。

此处以大堆为例。若创建堆的时候里面的元素小于K，则入队。用i来遍历100个数字，若其中有一个数字比堆顶元素小，则于与堆顶元素交换。

此处以10个数字取最小的3个数。

代码：

  1. public static void topk(int[] array,int k) {
  2.         PriorityQueue<Integer> maxHeap = new PriorityQueue<>(k, new Comparator<Integer>() {
  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.             if(maxHeap.size() < k) {
  11.                 maxHeap.offer(array[i]);
  12.             }else {
  13.                 int top = maxHeap.peek();
  14.                 if(top > array[i]) {
  15.                     maxHeap.poll();
  16.                     maxHeap.offer(array[i]);
  17.                 }
  18.             }
  19.         }
  20.         System.out.println(maxHeap);
  21.     }
  23.     public static void main(String[] args) {
  24.         int[] array = {1, 31, 2, 10, 7, 35, 21, 19, 56,45};//找到前3个最小的数据
  25.         topk(array, 3);
  26.     }
  27. //打印结果：  [7, 1, 2]

3.查找和最小的K对数字

对应leetcode题

思路：此题涉及到topK问题。但是与上面的topK问题又有些不同。因为要找和最小的K对数字，因此要创建大堆来找。整个方法的返回类型为List<List<Integer>>，则我们可以将每对数字看作一个List<Integer>类型。并且创建一个PriorityQueue只放入List<Integer>类型的数据。跟topK一样，如果其中有top > nums1[i]+nums2[j]，则top出队而nums1[i]与nums2[j]变为List<Integer>类型入队。最后队列中只剩下k对最小的数字，将它们存入到List<List<Integer>>类型中返回即可。

  1. class Solution {
  2.         public List<List<Integer>> kSmallestPairs(int[] nums1, int[] nums2, int k) {
  3.         PriorityQueue<List<Integer>> queue = new PriorityQueue<>(k, new Comparator<List<Integer>>(){
  4.             public int compare(List<Integer> o1,List<Integer> o2) {
  5.                 return (o2.get(0) + o2.get(1)) - (o1.get(0) + o1.get(1));
  6.             }
  7.         }); 
  8.         //取最小值是为了防止两个数组一个比较少的时候【1】  【1,2,3】
  9.         //并且nums1和nums2均为升序排列
  10.         for(int i = 0; i < Math.min(nums1.length, k); i++){
  11.             for(int j = 0; j < Math.min(nums2.length, k); j++){
  12.                 if(queue.size() < k) {
  13.                     List<Integer> pair = new ArrayList<>();
  14.                     pair.add(nums1[i]);
  15.                     pair.add(nums2[j]);
  16.                     queue.add(pair);
  17.                 }else {
  18.                     int top = queue.peek().get(0) + queue.peek().get(1);
  19.                     //大于K就出队列 
  20.                     if(top > nums1[i]+nums2[j]){
  21.                         List<Integer> pair = new ArrayList<>();
  22.                         queue.poll();
  23.                         pair.add(nums1[i]);
  24.                         pair.add(nums2[j]);
  25.                         queue.add(pair);
  26.                     }
  27.                 }
  28.             }
  29.         }
  30.         List<List<Integer>> res = new LinkedList<>();
  31.         for(int i =0; i < k && !queue.isEmpty(); i++){
  32.             res.add(queue.poll());
  33.         }
  34.         return res;
  35.     }
  36. }

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

原文链接 : https://blog.csdn.net/ZJRUIII/article/details/122507928

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

Java数据结构leetcode算法

相关文章

    查看更多

    热门标签

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

    最新文章

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