PriorityQueue优先级队列

偏执的太偏执、 2024-04-03 11:19 227阅读 0赞

文章目录

  • 1.概念
  • 2.优先级队列的模拟实现
    • 2.1 堆的概念
    • 2.2堆的创建
      • 2.2.1堆的向下调整
      • 2.2.2堆的构建
      • 2.2.3堆的插入
      • 2.2.4堆的删除
    • 2.3用堆模拟实现优先级队列
  • 3.常用接口介绍
    • 3.1PriorityQueue集合类源码分析
  • 4.堆的应用
    • 4.1 top-k问题最小的k个数
      • 思路1
      • 思路2
    • 4.2堆排序

1.概念

前面学过队列，队列是一种先进先出的数据结构，但有些情况下，操作的数据可能带有优先级，一般出队列时，可能需要优先级高的元素先出队列。

这种数据结构提供两个最基本的操作，返回最高优先级对象和添加新的对象(出队和入队)。

2.优先级队列的模拟实现

JDK1.8中的PriorityQueue底层使用了堆的数据结构，而堆实际就是在完全二叉树的基础之上进行了一些元素的调整。

2.1 堆的概念

如果有一个关键码的集合K = {k0，k1， k2，…，kn-1}，把它的所有元素按完全二叉树的顺序存储方式(分层遍历)存储 在一个一维数组中，并满足：Ki <= K2i+1 且 Ki<= K2i+2 (Ki >= K2i+1 且 Ki >= K2i+2) i = 0，1，2…，则称为小堆(或大堆)。将根节点最大的堆叫做最大堆或大根堆，根节点最小的堆叫做最小堆或小根堆。PriorityQueue默认是小根堆。

对于非完全二叉树，则不适合使用顺序方式进行存储，因为为了能够还原二叉树，空间中必须要存储空节
点，就会导致空间利用率比较低。

2.2堆的创建

2.2.1堆的向下调整

对于集合{ 27,15,19,18,28,34,65,49,25,37 }中的数据，如果将其创建成堆？

在这里插入图片描述

以大跟堆为例

思路：要想把这棵树变成大根堆，只需要将这棵树的每一棵子树都变成大根堆即可。

在这里插入图片描述
每一个绿框里都是一棵树，我们要把这些树都变成大根堆

在这里插入图片描述
在这里插入图片描述
在这里插入图片描述

  1. private void shiftDown(int root,int len) {
  3.         int parent=root;
  4.         int child=parent*2+1;
  5.         while(child<len){
  7.             if(child+1<len&&elem[child]<elem[child+1]){
  9.             //child+1可能会越界
  10.                 child++;
  11.             }
  12.             if(elem[child]>elem[parent]){
  14.                 int tmp=elem[child];
  15.                 elem[child]=elem[parent];
  16.                 elem[parent]=tmp;
  17.                 parent=child;
  18.                 child=parent*2+1;
  19.             }else{
  21.             //如果根节点大于孩子结点就不用向下遍历比较，因为就是从最后一棵子树向上调整的
  22.                 break;
  23.             }
  24.         }
  25.     }

向下调整的时间复杂度：O(log2(n))
n个结点树的高度是log2(n)，就是向下调整的次数

在这里插入图片描述

数组下标从后往前遍历，然后每个下标向下调整

2.2.2堆的构建

  1. public class PriorityQueue {
  3.     public int[] elem;
  4.     public int usedSize;
  5.     public static final int DEFAULT_CAPACITY=10;
  6.     public PriorityQueue() {
  8.         elem=new int[DEFAULT_CAPACITY];
  9.     }
  10.     /**
  11.      * 建堆的时间复杂度：O(n)
  12.      *
  13.      * @param array
  14.      */
  15.     public void createHeap(int[] array) {
  17.         for(int i=0;i<array.length;i++){
  19.             elem[i]=array[i];
  20.             usedSize++;
  21.         }
  23.         for(int parent=(elem.length-1)/2;parent>=0;parent--){
  25.             shiftDown(parent,elem.length);
  26.         }
  27.     }
  28. }
  30. public class Test {
  32.     public static void main(String[] args) {
  34.         int[] array={
  35.      27,15,19,18,28,34,65,49,25,37};
  36.         PriorityQueue priorityQueue=new PriorityQueue();
  37.         priorityQueue.createHeap(array);
  38.     }
  39. }

建堆的时间复杂度：O(n)

在这里插入图片描述

2.2.3堆的插入

在这里插入图片描述

在数组最后位置插入一个数，(数组满了则要扩容)只需要向上调整，直到child=0
其他子树都是大根堆不需要调整

  1. public void push(int val) {
  3.         if(isFull()){
  5.             //扩容
  6.             elem= Arrays.copyOf(this.elem,this.elem.length*2);
  7.         }
  8.         elem[usedSize]=val;
  9.         usedSize++;
  10.         shiftUp(usedSize-1);
  11.     }
  12.     private void shiftUp(int child) {
  14.         int parent=(child-1)/2;
  15.         while(child>0){
  17.             if(elem[parent]<elem[child]){
  19.                 int tmp=elem[parent];
  20.                 elem[parent]=elem[child];
  21.                 elem[child]=tmp;
  22.                 child=parent;
  23.                 parent=(child-1)/2;
  24.             }else{
  26.                 break;
  27.             }
  28.         }
  29.     }
  30.     public boolean isFull() {
  32.         return elem.length==usedSize;
  33.     }

插入后的结果：

在这里插入图片描述

2.2.4堆的删除

删除堆顶元素
将堆顶元素和最后一个元素交换，从堆顶开始向下调整

  1. /**
  2.      * 出队【删除】：每次删除的都是优先级高的元素
  3.      * 仍然要保持是大根堆
  4.      */
  5.     public void pollHeap() {
  7.         if(isEmpty()){
  9.             return;
  10.         }
  11.         int tmp=elem[0];
  12.         elem[0]=elem[elem.length-1];
  13.         elem[elem.length-1]=tmp;
  14.         usedSize--;
  15.         shiftDown(0,usedSize);
  16.     }
  17.     public boolean isEmpty() {
  19.         return usedSize==0;
  20.     }

结果：
在这里插入图片描述

2.3用堆模拟实现优先级队列

  1. import java.util.Arrays;
  2. public class PriorityQueue {
  4.     public int[] elem;
  5.     public int usedSize;
  6.     public static final int DEFAULT_CAPACITY=10;
  7.     public PriorityQueue() {
  9.         elem=new int[DEFAULT_CAPACITY];
  10.     }
  11.     /**
  12.      * 建堆的时间复杂度：O(n)
  13.      *
  14.      * @param array
  15.      */
  16.     public void createHeap(int[] array) {
  18.         for(int i=0;i<array.length;i++){
  20.             elem[i]=array[i];
  21.             usedSize++;
  22.         }
  24.         for(int parent=(elem.length-1)/2;parent>=0;parent--){
  26.             shiftDown(parent,elem.length);
  27.         }
  28.     }
  29.     /**
  30.      *
  31.      * @param root 是每棵子树的根节点的下标
  32.      * @param len  是每棵子树调整结束的结束条件
  33.      * 向下调整的时间复杂度：O(logn)
  34.      */
  35.     private void shiftDown(int root,int len) {
  37.         int parent=root;
  38.         int child=parent*2+1;
  39.         while(child<len){
  41.             if(child+1<len&&elem[child]<elem[child+1]){
  43.                 child++;
  44.             }
  45.             if(elem[child]>elem[parent]){
  47.                 int tmp=elem[child];
  48.                 elem[child]=elem[parent];
  49.                 elem[parent]=tmp;
  50.                 parent=child;
  51.                 child=parent*2+1;
  52.             }else{
  54.                 break;
  55.             }
  56.         }
  57.     }
  58.     /**
  59.      * 入队：仍然要保持是大根堆
  60.      * @param val
  61.      */
  62.     public void push(int val) {
  64.         if(isFull()){
  66.             //扩容
  67.             elem= Arrays.copyOf(this.elem,this.elem.length*2);
  68.         }
  69.         elem[usedSize]=val;
  70.         usedSize++;
  71.         shiftUp(usedSize-1);
  72.     }
  73.     private void shiftUp(int child) {
  75.         int parent=(child-1)/2;
  76.         while(child>0){
  78.             if(elem[parent]<elem[child]){
  80.                 int tmp=elem[parent];
  81.                 elem[parent]=elem[child];
  82.                 elem[child]=tmp;
  83.                 child=parent;
  84.                 parent=(child-1)/2;
  85.             }else{
  87.                 break;
  88.             }
  89.         }
  90.     }
  91.     public boolean isFull() {
  93.         return elem.length==usedSize;
  94.     }
  95.     /**
  96.      * 出队【删除】：每次删除的都是优先级高的元素
  97.      * 仍然要保持是大根堆
  98.      */
  99.     public void pollHeap() {
  101.         if(isEmpty()){
  103.             return;
  104.         }
  105.         int tmp=elem[0];
  106.         elem[0]=elem[elem.length-1];
  107.         elem[elem.length-1]=tmp;
  108.         usedSize--;
  109.         shiftDown(0,usedSize);
  110.     }
  111.     public boolean isEmpty() {
  113.         return usedSize==0;
  114.     }
  115.     /**
  116.      * 获取堆顶元素
  117.      * @return
  118.      */
  119.     public int peekHeap() {
  121.         if(isEmpty()){
  123.             return -1;
  124.         }
  125.         return elem[0];
  126.     }
  127. }

3.常用接口介绍

在这里插入图片描述

PriorityQueue默认是小根堆。

PriorityQueue中放置的元素必须要能够比较大小，不能插入无法比较大小的对象，否则会抛出ClassCastException异常

在这里插入图片描述

Student这个引用类型如果要进行比较，要实现Comparable<>接口,重写compareTo()方法

在这里插入图片描述

那么问题是它是什么时候在什么地方调用了我们重写的compareTo()方法？

3.1PriorityQueue集合类源码分析

分析PriorityQueue()构造方法：

  1. PriorityQueue<Student> priorityQueue=new PriorityQueue<>();

在这里插入图片描述

对offer()分析：

在这里插入图片描述
在这里插入图片描述

如果想实现大根堆,只需要修改compareTo()方法

  1. @Override
  2.     public int compareTo(Student o) {
  4.         return o.age-this.age;
  5.     }

那如果我想要Integer类型的元素变成大根堆？
Integer源码不能修改compareTo()方法
所以就用到comparator比较器

  1. class IntCmp implements Comparator<Integer> {
  3.     @Override
  4.     public int compare(Integer o1, Integer o2) {
  6.         return o2.compareTo(o1);
  7.     }
  8. }
  9. public class Test {
  11.     public static void main(String[] args) {
  13.         PriorityQueue<Integer> priorityQueue=new PriorityQueue<>(new IntCmp());
  14.         priorityQueue.offer(10);
  15.         priorityQueue.offer(20);
  16.         priorityQueue.offer(3);
  17.         System.out.println(priorityQueue.poll());
  18.         System.out.println(priorityQueue.poll());
  19.         System.out.println(priorityQueue.poll());
  20.     }
  21. }

在这里插入图片描述

当没有传入数组容量时，默认容量是11，
当没有比较器时，必须是可比较的
优先使用比较器

  1. //匿名内部类
  2. public static void main(String[] args) {
  4.         PriorityQueue<Integer> priorityQueue=new PriorityQueue<>(new Comparator<Integer>() {
  6.             @Override
  7.             public int compare(Integer o1, Integer o2) {
  9.                 return o2.compareTo(o1);
  10.             }
  11.         });
  12.     }
  14. //lambda表达式
  15. PriorityQueue<Integer> priorityQueue2=new PriorityQueue<>((x,y)->{
  16.     return x.compareTo(y);});
  17. PriorityQueue<Integer> priorityQueue3=new PriorityQueue<>((x,y)->x.compareTo(y));

在这里插入图片描述
PriorityQueue是如何扩容的？
在这里插入图片描述

如果增加一个元素数组满了就扩容，根据原来数组的容量和64比较来决定是2倍扩还是1.5倍扩。扩容后新的容量如果大于整数最大值-8要进行调整，minCapacity是原来数组容量+1，如果minCapacity>整数最大值-8,就调整为整数最大值，否则就给整数最大值-8。

4.堆的应用

4.1 top-k问题最小的k个数

在这里插入图片描述
能想到的最简单直接的方式就是排序，但是如果数据量非常大，排序就不太可取了(可能数据都不能一下子全部加载到内存中)。最佳的方式就是用堆来解决。

思路1

把arr数组所有元素建成小根堆，出队前k个元素，每出队1个，自动调整成小根堆，每次弹出的都是堆顶元素，自然是最小的。

时间复杂度：O(n+klogn)
建堆：O(n)
调整：O(klogn)

  1. public static int[] smallestK2(int[] arr, int k) {
  3.         //1.建立一个小根堆
  4.         PriorityQueue<Integer> minHeap=new PriorityQueue<>();
  5.         //2.遍历数组，将数组的每个元素放到小根堆里
  6.         for (int i = 0; i < arr.length; i++) {
  8.             minHeap.offer(arr[i]);
  9.         }
  11.         //3.弹出k个元素，放到数组中，返回即可
  12.         int[] tmp=new int[k];
  13.         for (int i = 0; i < k; i++) {
  15.             tmp[i]=minHeap.poll();
  16.         }
  17.         return tmp;
  18.     }

如果想降低时间复杂度，下面给出第二种做法。

思路2

将前k个元素建成大根堆，遍历数组中剩下的元素，如果比堆顶元素小，则弹出堆顶元素，然后offer(),并调整为大根堆，遍历结束后堆里就是最小的k个数。
(和思路一的区别是没有整体建堆)

这里的k是很小的

时间复杂度：O(nlogk)
O(k+(n-k)logk)=O(k+nlogk-klogk)=O(nlogk)

  1. class Solution {
  3.     public int[] smallestK(int[] arr, int k) {
  5.         PriorityQueue<Integer> maxHeap=new PriorityQueue<>(k, new Comparator<Integer>() {
  7.             @Override
  8.             public int compare(Integer o1, Integer o2) {
  10.                 return o2.compareTo(o1);
  11.             }
  12.         });
  13.         for(int i=0;i<arr.length;i++){
  15.             if(maxHeap.size()<k){
  17.                 maxHeap.offer(arr[i]);
  18.             }else{
  20.                 int val=maxHeap.peek();
  21.                 if(arr[i]<val){
  23.                     maxHeap.poll();
  24.                     maxHeap.offer(arr[i]);
  25.                 }
  26.             }
  27.         }
  28.         int[] tmp=new int[k];
  29.         for (int i = 0; i < k; i++) {
  31.             tmp[i]=maxHeap.poll();
  32.         }
  33.         return tmp;
  34.     }
  35. }

在这里插入图片描述
这样写抛异常了，原因是没有判断k是否合法
在这里插入图片描述
正确写法：

  1. class Solution {
  3.     public int[] smallestK(int[] arr, int k) {
  5.         if(arr==null||k==0){
  7.             return new int[0];
  8.         }
  9.         PriorityQueue<Integer> maxHeap=new PriorityQueue<>(k, new Comparator<Integer>() {
  11.             @Override
  12.             public int compare(Integer o1, Integer o2) {
  14.                 return o2.compareTo(o1);
  15.             }
  16.         });
  17.         for(int i=0;i<arr.length;i++){
  19.             if(maxHeap.size()<k){
  21.                 maxHeap.offer(arr[i]);
  22.             }else{
  24.                 int val=maxHeap.peek();
  25.                 if(arr[i]<val){
  27.                     maxHeap.poll();
  28.                     maxHeap.offer(arr[i]);
  29.                 }
  30.             }
  31.         }
  32.         int[] tmp=new int[k];
  33.         for (int i = 0; i < k; i++) {
  35.             tmp[i]=maxHeap.poll();
  36.         }
  37.         return tmp;
  38.     }
  39. }

如果要求第k小的，就是大根堆堆顶元素

4.2堆排序

利用堆的思想来排序

升序：建大根堆

要想实现升序，如果建小根堆，然后分层弹出，还有另外设一个空间来存放这些弹出的数据，空间复杂度是O(n)。况且小根堆中的元素也不一定是升序的。

如果考虑建大根堆，让大根堆堆顶元素和最后一个交换，然后再向下调整成大根堆，然后再让大根堆堆顶元素和最后一个交换，并向下调整成大根堆…以此类推。

在这里插入图片描述

  1. public class TestHeap {
  3.     public int[] elem;
  4.     public int usedSize;
  5.     public static final int DEFAULT_CAPACITY=10;
  6.     public TestHeap() {
  8.         elem=new int[DEFAULT_CAPACITY];
  9.     }
  10.     /**
  11.      * 建堆的时间复杂度：O(n)
  12.      *
  13.      * @param array
  14.      */
  15.     public void createHeap(int[] array) {
  17.         for(int i=0;i<array.length;i++){
  19.             elem[i]=array[i];
  20.             usedSize++;
  21.         }
  23.         for(int parent=(usedSize-1-1)/2;parent>=0;parent--){
  25.             shiftDown(parent,usedSize);
  26.         }
  27.     }
  28. }
  29. private void shiftDown(int root,int len) {
  31.         int parent=root;
  32.         int child=parent*2+1;
  33.         while(child<len){
  35.             if(child+1<len&&elem[child]<elem[child+1]){
  37.                 child++;
  38.             }
  39.             if(elem[child]>elem[parent]){
  41.                 int tmp=elem[child];
  42.                 elem[child]=elem[parent];
  43.                 elem[parent]=tmp;
  44.                 parent=child;
  45.                 child=parent*2+1;
  46.             }else{
  48.                 break;
  49.             }
  50.         }
  51.     }
  52.     public void heapSort(){
  54.         int end=usedSize-1;
  55.         while(end>0){
  57.             int tmp=elem[0];
  58.             elem[0]=elem[end];
  59.             elem[end]=tmp;
  60.             shiftDown(0,end);
  61.             end--;
  62.         }
  63.     }
  64.     public static void main5(String[] args) {
  66.         int[] array={
  67.      27,15,19,18,28,34,65,49,25,37};
  68.         TestHeap testHeap=new TestHeap();
  69.         testHeap.createHeap(array);
  70.         testHeap.heapSort();
  71.     }

时间复杂度：O(n)+O(nlogn)约等于O(nlogn)
空间复杂度：O(1)

发表评论

表情：
评论列表 （有 0 条评论，227人围观）

还没有评论，来说两句吧...

相关阅读

    相关 PriorityQueue(优先级队列总结)

    一，概念 > 队列是一种先进先出(FIFO)的数据结构，但有些情况下，操作的数据可能带有优先级，一般出队列时，可能需要优先级高的元素先出队列 > 数据结构应该

    怼烎@怼烎@/ 0 赞/ 184 阅读