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

PriorityQueue优先级队列的使用和Top-k问题

article 2025/2/11 15:13:55

关于PriorityQueue的使用注意：

1.使用时必须导入 PriorityQueue 所在的包：

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

3.不能插入 null 对象，否则会抛出NullPointerException

4.没有容量限制，可以插入任意多个元素，其内部可以自动扩容。

5.PriorityQueue底层使用了堆数据结构，默认情况下是小堆---即每次获取到的元素都是最小的元素。

PriorityQueue优先级队列的构造：

第一种：

第二种：

建立大根堆的PriorityQueue

PriorityQueue优先级队列的方法：

不同阶段的扩容规则

1. 容量小于 64 时

2. 容量大于等于 64 时

3. 容量超过 MAX_ARRAY_SIZE 时

top-k问题：最大或者最小的前k个数据。

方法一（利用PriorityQueue优先级队列）：

方法二（建立大小为k的大根堆）：

获取前k个最小的数：题目链接

Java集合框架中提供了PriorityQueue和PriorityBlockingQueue两种类型的优先级队列， PriorityQueue是线程不安全的，PriorityBlockingQueue是线程安全的。

这里我们主要介绍PriorityQueue：

关于PriorityQueue的使用注意：

1.使用时必须导入 PriorityQueue 所在的包：

import java.util.PriorityQueue;

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

PriorityQueue 要求元素能够比较大小，是为了实现其内部的排序功能，确保每次取出的元素都是优先级最高的元素。

3.不能插入 null 对象，否则会抛出NullPointerException

4.没有容量限制，可以插入任意多个元素，其内部可以自动扩容。

5.PriorityQueue底层使用了堆数据结构，默认情况下是小堆---即每次获取到的元素都是最小的元素。

PriorityQueue优先级队列的构造：

第一种：

// 创建⼀个空的优先级队列，底层默认容量是 11 
 PriorityQueue<Integer> q1 = new PriorityQueue<>();

第二种：

// 创建⼀个空的优先级队列，容量为a
 PriorityQueue<Integer> q2 = new PriorityQueue<>(a);

注意：a不能小于1，否则会抛异常。

建立大根堆的PriorityQueue

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

// ⽤⼾⾃⼰定义的⽐较器：直接实现Comparator接⼝，然后重写该接⼝中的compare⽅法即可
class IntCmp implements Comparator<Integer> {
    @Override
    public int compare(Integer o1, Integer o2) {
        return o2-o1;
    }
}

IntCmp 是比较器类名。

对比：

默认情况下的小根堆：

 PriorityQueue<Integer> p1 = new PriorityQueue<>();
        p1.offer(6);
        p1.offer(10);
        p1.offer(5);
        p1.offer(8);
        System.out.println(p1.peek());

程序运行结果：

使用了比较器创建的大根堆：

class MaxC implements Comparator<Integer> {
    @Override
    public int compare(Integer o1, Integer o2) {
        return o2-o1;
    }
}

public class Test {

    public static void main(String[] args) {

        PriorityQueue<Integer> p1 = new PriorityQueue<>(new MaxC());
        p1.offer(6);
        p1.offer(10);
        p1.offer(5);
        p1.offer(8);
        System.out.println(p1.peek());

    }
}

程序运行结果：

PriorityQueue优先级队列的方法：

不同阶段的扩容规则

1. 容量小于 64 时

当队列当前容量（即底层数组的长度）小于 64 时，每次扩容会将容量扩展为原来的 2 倍。例如，初始容量为 16，当元素数量超过 16 时，队列会进行扩容，新的容量变为 16 * 2 = 32；若再次触发扩容，容量会变为 32 * 2 = 64。

2. 容量大于等于 64 时

当队列当前容量大于等于 64 时，每次扩容会将容量扩展为原来的 1.5 倍。例如，当容量达到 64 并触发扩容时，新的容量变为 64 + 64 / 2 = 96。

3. 容量超过 `MAX_ARRAY_SIZE` 时

MAX_ARRAY_SIZE 是一个预定义的最大数组长度限制。当按照上述规则计算得到的新容量超过这个限制时，会将容量设置为 MAX_ARRAY_SIZE。这是为了避免创建过大的数组，防止出现内存溢出等问题。

top-k问题：最大或者最小的前k个数据。

这里我们解决的是前k个最小的数据。

假如给出一个数组，取出数组 k 个最小的个元素。

方法一（利用PriorityQueue优先级队列）：

代码实现：

 public static int[] topk1(int[] array,int k) {
        PriorityQueue<Integer> p1 = new PriorityQueue<>();

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

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

    public static void main(String[] args) {

        int[] array = {1,12,3,41,5,16,7,81,9,10};
        int[] ret = topk1(array, 5);
        System.out.println(Arrays.toString(ret));

    }

代码运行结果：

方法二（建立大小为k的大根堆）：

代码实现：

class ImpLess implements Comparator<Integer> {

    @Override
    public int compare(Integer o1, Integer o2) {
        return o2-o1;
    }
}

public class Test {

    public static int[] topk(int[] array,int k) {
        PriorityQueue<Integer> p1 = new PriorityQueue<>(k,new ImpLess());

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

        for (int i = k; i < array.length; i++) {
            if(p1.peek() > array[i]) {
                p1.poll();
                p1.offer(array[i]);
            }
        }

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

    public static void main(String[] args) {

        int[] array = {1,12,3,41,5,16,7,81,9,10};
        int[] ret = topk(array, 5);
        System.out.println(Arrays.toString(ret));

    }
}

运行结果：

可以看到，结果也是正确的。

分析：

我们建立了一个大小为k的大根堆，先拿数组前k个元素插入堆里，由于建立的是大根堆，堆顶元素是最大的，那么只要遍历剩余的数组元素并于堆顶元素比较，如果堆顶元素比数组元素大了，删除堆顶元素，PriorityQueue会自动向下调整，之后还是大根堆，依次遍历完数组，就能得到k个最小的元素了。

方法二也是优解。

获取前k个最小的数：题目链接

这题的思路与上面两个方法逻辑是一样的。

题解代码：

class Imbig implements Comparator<Integer> {
    @Override
    public int compare(Integer o1, Integer o2) {
        return o2-o1;
    }
}

class Solution {
    public int[] smallestK(int[] arr, int k) {
     int[] array = new int[k];
        if(k <= 0) {
            return array;
        }

    PriorityQueue<Integer> list = new PriorityQueue<>(new Imbig());

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

    for(int i = k;i < arr.length;i++) {
        int count = list.peek();
        if(count > arr[i]) {
            list.poll();
            list.offer(arr[i]);
        }
    }

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

    return array;

    }
    
}

查看全文

http://www.kler.cn/a/540803.html