devbox
我家小花儿
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

【Java】PriorityQueue优先级队列（堆）+比较器详解

作者：我家小花儿 | 2024-04-03 10:12:07

赞

踩

【Java】PriorityQueue优先级队列（堆）+比较器详解

目录

铺垫

堆

建堆

基本公式

调整为大(小)根堆

堆的增加

堆的删除 

 正文：

比较

重写基类的equals()比较方法：

内部比较器——Comparable.compareTo(E o)：

外部比较器——Comparator.compare(T o1, T o2)：

源码粗略分析

常用构造方法

实现Comparable接口 

实现Comparator接口

改为大根堆

对于基本类型：

对于引用类型：

比较器快速写法

铺垫

堆

优先级队列的底层是一个数组，但这个数组又比较特殊——二叉树通过层序遍历存放到该数组的数据。这样存放的方式就是堆这种数据结构。

大根堆：如果在堆中，每个根结点的值大于两个孩子结点的值。（对左右孩子无要求）

小根堆：如果在堆中，每个根结点的值小于两个孩子结点的值。（对左右孩子无要求）

建堆

基本公式

调整为大(小)根堆

在一个一维数组中：

1.对于每一个根结点都要调整为大小根堆。

2.调整时，先要找到较大的孩子

3.然后二者交换，继续向下调整该根结点下面的结点。

4.调整时可能会存在越界的情况，孩子结点可能会越界。

  1.     public void createHeap() {
  2.         //建大根堆
  3.         //对每一个根节点使用向下调整算法
  4.         //最后一个孩子 c = length - 1
  5.         //c = 2 * p +1
  6.         //p = (c - 1)/2
  7.         for (int parent = (array.length - 1 -1) / 2; parent >= 0; parent--) {
  8.             shiftDown(parent, usedSize);
  9.         }
  10.     }
  11.     //向下调整
  12.     private void shiftDown(int parent, int length) {
  13.         int child = 2 * parent + 1;
  14.         while (child < length) {
  15.                //先判断孩子是否越界
  16.             if (child < length - 1 && array[child] < array[child + 1]) {
  17.                 child++;
  18.             }
  19.             if (array[parent] < array[child]) {
  20.                 swap(array, parent, child);
  21.                 parent = child;
  22.                 child = 2 * parent + 1;
  23.             } else {
  24.                 break;
  25.             }
  26.         }
  27.     }
  28.  
  29.     private void swap(int[] array, int x, int y) {
  30.         int tmp = array[x];
  31.         array[x] = array[y];
  32.         array[y] = tmp;
  33.     }

堆的增加

在堆里添加完数据后，应该还要保证堆为大(小)根堆。

1.判断堆是否满了，满了扩容。

2.把添加的数据放到数组的最后面。

3.找到最后一个结点的父亲结点，向上调整。

4.(建大堆)如果父亲结点比孩子结点小，就调整，然后，父亲结点指向孩子结点，重新计算父亲结点，直到最后一个孩子调整完。

5.useSized++

 

堆的删除 

优先级队列，是对于某些数据优先操作的结构，所以很自然的我们要优先对堆顶数据进行删除。

1.判断堆是否为空，为空抛出异常。

2.堆顶数据与最后一个结点进行交换。

3.对堆顶使用一次向下调整即可恢复成大(小)根堆。

4.useSized--

  1.     public void pop() {
  2.         if (isEmpty()) {
  3.             return;
  4.         }
  5.         swap(array, 0, usedSize - 1);
  6.         usedSize--;
  7.         shiftDown(0, usedSize);
  8.     }

 正文：

有了以上概念，我们就能更容易理解PriorityQueue的源码部分的实现。

比较

在生成大小根堆的时候，数据是通过比较大小来排序的。所以PriorityQueue底层必定有比较数据大小的东西。

重写基类的equals()比较方法：

所有的类都是继承Object类的，Object类中就有equals()方法。

重写equals()方法用到这里显然不合适，因为该方法只能比较二者是否想等，无法比较出大小关系。

内部比较器——Comparable<E>.compareTo(E o)：

Comparable是JDK提供的泛型接口类，源码如下：

  1. //Compareble是java.lang中的接口类，可以直接使用
  2. public interface Comparable<E> {
  3.     // 返回值:
  4.     // < 0: 表示 this 指向的对象小于形参 o 指向的对象
  5.     // == 0: 表示 this 指向的对象等于形参 o 指向的对象
  6.     // > 0: 表示 this 指向的对象大于形参 o 指向的对象
  7.     int compareTo(E o);
  8. }
  9.  
  10. //对象支持自己与自己比较
  11. //实现了该接口的类就可以自动进行排序
  12. //集合通过Collection.sort()排序，数组通过Arrays.sort()进行排序

该方法可以比较出数据的大小，所以我们可以在定义类的时候实现该接口，重写方法就可以比较。

外部比较器——Comparator<T>.compare(T o1, T o2)：

  1. //Comparator是java.util 包中的泛型接口类，使用时必须导入对应的包
  2.  
  3. public interface Comparator<T> {
  4. // 返回值:
  5. // < 0: 表示 o1 指向的对象小于 o2 指向的对象
  6. // == 0: 表示 o1 指向的对象等于 o2 指向的对象
  7. // > 0: 表示 o1 指向的对象等于 o2 指向的对象
  8. int compare(T o1, T o2);
  9. }
  10.  
  11. //使用Comparator的情况：
  12. //1.没有实现Comparable接口
  13. //2.实现了Comparable接口，但是其中的compareTo方法不符合自己的预期

源码粗略分析

  1.     public static void main(String[] args) {
  2.         PriorityQueue<Integer>  priorityQueue1= new PriorityQueue<>();
  3.         priorityQueue1.offer(4);
  4.         priorityQueue1.offer(6);
  5.         priorityQueue1.offer(3);
  6.         System.out.println(priorityQueue1);
  7.     }

 

若是其他引用类型，就不可以这样offer()了，在offer()第二个数据的时候就会抛异常。

  1. class Student {
  2.     public String name;
  3.     public int age;
  4.  
  5.     public Student (int age) {
  6.         this.age = age;
  7.     }
  8. }
  9.  
  10. public class Test {
  11.     public static void main(String[] args) {
  12.         PriorityQueue<Integer>  priorityQueue1= new PriorityQueue<>();
  13.         priorityQueue1.offer(4);
  14.         priorityQueue1.offer(6);
  15.         priorityQueue1.offer(3);
  16.         System.out.println(priorityQueue1);
  17.  
  18.         PriorityQueue<Student>  priorityQueue2 = new PriorityQueue<>();
  19.         priorityQueue2.offer(new Student(20));
  20.         priorityQueue2.offer(new Student(22));
  21.     }
  22. }

常用构造方法

第一种：什么都不传，那么默认空间大小为11，无比较器

第二种：只传空间大小，此时空间大小为所传的值

第三种：只传比较器，下面详解比较器作用

实现Comparable接口 

  1. class Student implements Comparable<Student> {
  2.     public String name;
  3.     public int age;
  4.  
  5.     public Student (int age) {
  6.         this.age = age;
  7.     }
  8.  
  9.     @Override
  10.     public int compareTo(Student o) {
  11.         return this.age - o.age;
  12.     }
  13.  
  14.     @Override
  15.     public String toString() {
  16.         return "Student{" +
  17.                 "name='" + name + '\'' +
  18.                 ", age=" + age +
  19.                 '}';
  20.     }
  21. }
  22.  
  23. public class Test {
  24.     public static void main(String[] args) {
  25.         PriorityQueue<Integer>  priorityQueue1= new PriorityQueue<>();
  26.         priorityQueue1.offer(4);
  27.         priorityQueue1.offer(6);
  28.         priorityQueue1.offer(3);
  29.         System.out.println(priorityQueue1);
  30.  
  31.         PriorityQueue<Student>  priorityQueue2 = new PriorityQueue<>();
  32.         priorityQueue2.offer(new Student(20));
  33.         priorityQueue2.offer(new Student(22));
  34.         priorityQueue2.offer(new Student(23));
  35.         System.out.println(priorityQueue2);
  36.     }
  37. }

 当实现了Comparable接口后，重写CompareTo方法后，此时就可以比较引用类型了。

此时它应该执行到一下源码部分。

实现Comparator接口

  1. class Student {
  2.     public String name;
  3.     public int age;
  4.  
  5.     public Student (int age) {
  6.         this.age = age;
  7.     }
  8.  
  9.  
  10.     @Override
  11.     public String toString() {
  12.         return "Student{" +
  13.                 "name='" + name + '\'' +
  14.                 ", age=" + age +
  15.                 '}';
  16.     }
  17. }
  18. class StuCompare implements Comparator<Student> {
  19.     @Override
  20.     public int compare(Student o1, Student o2) {
  21.         return o2.age - o1.age;
  22.     }
  23. }
  24.  
  25. public class Test {
  26.     public static void main(String[] args) {
  27.         PriorityQueue<Integer>  priorityQueue1= new PriorityQueue<>();
  28.         priorityQueue1.offer(4);
  29.         priorityQueue1.offer(6);
  30.         priorityQueue1.offer(3);
  31.         System.out.println(priorityQueue1);
  32.  
  33.         PriorityQueue<Student>  priorityQueue2 = new PriorityQueue<>(new StuCompare());
  34.         priorityQueue2.offer(new Student(20));
  35.         priorityQueue2.offer(new Student(22));
  36.         priorityQueue2.offer(new Student(23));
  37.         System.out.println(priorityQueue2);
  38.     }
  39. }

通过自定义的比较器，并且通过传入比较器的构造方法后，我们也可以比较。

此时它应该执行到下面的源码部分。

改为大根堆

因为源码默认建小根堆，如果我们想建大根堆，有了以上源码分析，我们不难发现，关键就在比较器上，我们只需要改变比较规则，就可以建立大根堆。

对于基本类型：

比如Integer，我们无法到源码中改变比较规则，所以只能传比较器，这样会优先使用有比较器的方法。

  1. class IntCompare implements Comparator<Integer> {
  2.     @Override
  3.     public int compare (Integer o1, Integer o2) {
  4.         return o2.compareTo(o1);
  5.     }
  6. }
  7. public class Test {
  8.     public static void main(String[] args) {
  9.         PriorityQueue<Integer>  priorityQueue1= new PriorityQueue<>(new IntCompare());
  10.         priorityQueue1.offer(4);
  11.         priorityQueue1.offer(6);
  12.         priorityQueue1.offer(3);
  13.         System.out.println(priorityQueue1);
  14.     }
  15. }

 

对于引用类型：

若该引用类型实现了Comparable接口，我们直接修改compareTo

若没有，则修改比较器中的compare

  1.     class Student implements Comparable<Student> {
  2.     public String name;
  3.     public int age;
  4.  
  5.     public Student (int age) {
  6.         this.age = age;
  7.     }
  8.  
  9.     @Override
  10.     public int compareTo(Student o) {
  11.         return o.age - this.age;
  12.     }
  13.  
  14.     @Override
  15.     public String toString() {
  16.         return "Student{" +
  17.                 "name='" + name + '\'' +
  18.                 ", age=" + age +
  19.                 '}';
  20.         }
  21.     }
  22.  
  23.  
  24.  
  25. public class Test {
  26.     public static void main(String[] args) {
  27.         PriorityQueue<Student>  priorityQueue2 = new PriorityQueue<>();
  28.         priorityQueue2.offer(new Student(20));
  29.         priorityQueue2.offer(new Student(22));
  30.         priorityQueue2.offer(new Student(23));
  31.         System.out.println(priorityQueue2);
  32.     }
  33. }

 ​​​​​

 

  1. class Student {
  2.     public String name;
  3.     public int age;
  4.  
  5.     public Student (int age) {
  6.         this.age = age;
  7.     }
  8.  
  9.  
  10.     @Override
  11.     public String toString() {
  12.         return "Student{" +
  13.                 "name='" + name + '\'' +
  14.                 ", age=" + age +
  15.                 '}';
  16.     }
  17. }
  18.  
  19. class StuCompare implements Comparator<Student> {
  20.     @Override
  21.     public int compare(Student o1, Student o2) {
  22.         return o2.age - o1.age;
  23.     }
  24. }
  25.  
  26. public class Test {
  27.     public static void main(String[] args) {
  28.         PriorityQueue<Student>  priorityQueue2 = new PriorityQueue<>(new StuCompare());
  29.         priorityQueue2.offer(new Student(20));
  30.         priorityQueue2.offer(new Student(22));
  31.         priorityQueue2.offer(new Student(23));
  32.         System.out.println(priorityQueue2);
  33.     }
  34. }

比较器快速写法

  1. class Student {
  2.     public String name;
  3.     public int age;
  4.  
  5.     public Student (int age) {
  6.         this.age = age;
  7.     }
  8.  
  9.     @Override
  10.     public String toString() {
  11.         return "Student{" +
  12.                 "name='" + name + '\'' +
  13.                 ", age=" + age +
  14.                 '}';
  15.     }
  16. }
  17.  
  18. public class Test {
  19.     public static void main(String[] args) {
  20.         //这里直接new了一个比较器传过去了
  21.         PriorityQueue<Student>  priorityQueue2 = new PriorityQueue<>(new Comparator<Student>() {
  22.             @Override
  23.             public int compare(Student o1, Student o2) {
  24.                 return o1.age - o2.age;
  25.             }
  26.         });
  27.         priorityQueue2.offer(new Student(20));
  28.         priorityQueue2.offer(new Student(22));
  29.         priorityQueue2.offer(new Student(23));
  30.         System.out.println(priorityQueue2);
  31.     }
  32.  
  33.     public static void main1(String[] args) {
  34.         MyPriorityQueue heap = new MyPriorityQueue();
  35.         int[] arr = {27, 15, 19, 18, 28, 34, 65, 49, 25, 37};
  36.         heap.initArray(arr);
  37.         heap.createHeap();
  38.         heap.push(100);
  39.         //heap.pop();
  40.  
  41.         PriorityQueue<Integer>  priorityQueue1= new PriorityQueue<>();
  42.         priorityQueue1.offer(4);
  43.         priorityQueue1.offer(6);
  44.         priorityQueue1.offer(3);
  45.         System.out.println(priorityQueue1);
  46.  
  47.     }
  48. }

有什么错误评论区指出，希望可以帮到你。

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/我家小花儿/article/detail/355108?site
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号