当前位置：首页 > article >正文

java数据结构_优先级队列（堆）_6.2

article 2025/2/26 6:05:14

3. 常用接口

3.1 PriorityQueue的特性

Java集合框架中提供了PriorityQueue和PriorityBlockingQueue两种类型的优先级队列，PriorityQueue的线性不安全的，PriorityBlockingQueue是线程安全的，这里主要介绍PriorityQueueu。

关于PriorityQueue的使用要注意：

使用时需要导包，即 import java.util.PriorityQueue;
PriorityQueue中放置的元素必须要能够比较大小，不能擦汗如无法比较大小的对象，否则会抛出ClassCastException异常，如下图
不能插入null对象，否则会抛出NullPointerException
“没有容量限制”，可以插入任意多个元素，因为其内部利用Array.copyOf可以自动扩容
插入和删除元素的时间复杂度为O(log2N)
底层使用的是堆结构
其默认情况下是小根堆 --> 即每次获得到的元素第是最小的元素

3.2 PriorityQueue常用接口介绍

1.优先级队列的构造

在IDEA中的PriorityQueue的Structure中可以看到PriorityQueue有多种构造方法

下面为相关源码实现，此处仅作列举，后面会讲解

总结：

使用：

默认情况下，PriorityQueue队列是小根堆，如果需要是大根堆，需要用户提供比较器：

此处先不作介绍，铺垫一下

2. 插入 / 删除 / 获取优先级最高的元素

就是方法的使用，很简单

补充：JDK1.8中，PriorityQueue的扩容方式：

4. Top - k问题

TOP-K问题：即求数据集合中前K个最大的元素或者最小的元素，一般情况下数据量都比较大。比如：专业前10名、世界500强、富豪榜、游戏中前100的活跃玩家等。

做法1：把数组进行排序排序之后取出前K个最大的或者最小的。但是，当数据量非常大的时候，无法再内存中进行排序。

做法2：把所有数据都放入优先级队列中，前K个最大值，就用大根堆，前K个最小值，就用小根堆，出队K次即可。但是，仍然是上面的问题，如果数据量非常大的时候，是无法把所有的数据都放入优先级队列的。

代码如下：

public int[] smallestK(int[] array, int k) {
    int[] ret = new int[k];
    if(array == null || k <= 0) {
        return ret;
    }

    PriorityQueue<Integer> p = new PriorityQueue<>(array.length);

    for(int i = 0; i < array.length; i++) {
        p.offer(array[i]);
    }

    for(int i = 0; i < k; i++) {
        ret[i] = p.poll();
    }
    return ret;
}

且上面两种方法还有一点不好的地方是：效率十分低下。

建议的做法：

如果求前K个最小的数据，可以创建一个容量为K的大根堆，先添加K个元素进入这个大根堆中，然后将剩下的元素，每次都和堆顶元素进行比较，如果比堆顶小（如果该元素比堆顶元素小，又因为是大根堆，则堆顶元素一定不是前K个最小的元素之一），那么堆进行出队操作，然后把当前数组中的元素存放到大小为K的大根堆中。

如下图：求前3个最小的元素，先创建一个容量为3的大根堆

然后再将剩余的元素9，2逐个和堆顶元素进行比较，如果小于该堆顶元素，就进行出队操作，然后把当前数组中的元素存放到大小为K的大根堆中

最终得到的容量为K的大根堆，就是前K个最小的元素

同样的，如果求的是前K个最大的数据，则创建一个容量为K的小根堆，然后堆顶元素和数组中的元素进行比较，如果数组元素比堆顶元素大，则进行出队操作，然后将数组元素入队。

求前K个最大的数据的代码如下：

public int[] maxLestK(int[] array, int k) {
    int[] ret = new int[k];

    if(array == null || k <= 0) {
        return ret;
    }
    
    PriorityQueue<Integer> priorityQueue = new PriorityQueue<>();

    for(int i = 0; i < k; i++) {
        priorityQueue.offer(array[i]);
    }

    for(int i = k; i < array.length; i++) {
        int top = priorityQueue.peek();
        
        if(array[i] > top) {
            priorityQueue.poll();
            priorityQueue.offer(array[i]);
        } 
    }
    
    for(int i = 0; i < k; i++) {
        ret[i] = priorityQueue.poll();
    }
    return ret;
}