有界优先队列 - BoundedPriorityQueue

简介

BoundedPriorityQueue 是 Hutool 提供的一个有界优先队列，用于处理在大量数据中获取前 N 个最大或最小元素的场景。与传统优先队列不同，BoundedPriorityQueue 在超出容量时会自动丢弃不符合优先级的元素，从而保证空间利用率。

1. 使用场景

假设我们有一个分布式系统，每个数据库实例保存了部分用户信息。我们希望找到这些用户中最热门的前 5 名。通过在每个数据库实例上找出前 5 名，再合并这些部分结果并进行排序，我们可以得到最终的结果。BoundedPriorityQueue 简化了这个过程，只需将数据依次加入队列，队列会自动维护前 5 名元素。

2. 主要方法

2.1 构造方法

BoundedPriorityQueue 提供了多种构造方式，允许自定义容量、比较器等。

• BoundedPriorityQueue(int capacity)：创建一个有界优先队列，使用默认的自然顺序排序。
• BoundedPriorityQueue(int capacity, Comparator<? super T> comparator)：创建一个有界优先队列，使用自定义的比较器进行排序。

示例：构造有界优先队列

import cn.hutool.core.collection.BoundedPriorityQueue;
import java.util.Comparator;

public class BoundedPriorityQueueExample {
    public static void main(String[] args) {
        // 使用默认的自然顺序，创建容量为 5 的有界优先队列
        BoundedPriorityQueue<Integer> queue = new BoundedPriorityQueue<>(5);

        // 使用自定义比较器，按从大到小排序
        BoundedPriorityQueue<Integer> customQueue = new BoundedPriorityQueue<>(5, Comparator.reverseOrder());

        // 打印队列信息
        System.out.println("默认自然顺序队列: " + queue);
        System.out.println("自定义比较器队列: " + customQueue);
    }
}

• 参数说明：

  • capacity: 队列的容量，即最多存储多少个元素。
  • comparator: 自定义的比较器，用于定义排序规则。如果未指定，使用元素的自然顺序。

• 作用：用于初始化队列，定义其容量和排序规则。

• 实际开发场景：在需要获取大量数据中的前 N 个最大或最小元素时，可以使用此构造方法创建合适的队列。

2.2 添加元素

通过 offer 或 add 方法将元素加入队列。如果队列已满且新元素优先级低于当前队列中的元素，则新元素会被自动丢弃。

示例：添加元素并维护队列前 N 名

import cn.hutool.core.collection.BoundedPriorityQueue;

public class BoundedPriorityQueueExample {
    public static void main(String[] args) {
        // 创建一个容量为 5 的有界优先队列，按自然顺序排序
        BoundedPriorityQueue<Integer> queue = new BoundedPriorityQueue<>(5);

        // 定义一个包含 6 个元素的数组
        int[] array = new int[]{5, 7, 9, 2, 3, 8};

        // 依次将元素加入队列
        for (int i : array) {
            queue.offer(i);
        }

        // 打印队列结果，预期为前 5 小的元素
        System.out.println("队列中的前 5 名元素: " + queue);
    }
}

• 方法签名：
  • boolean offer(T e)：将元素加入队列。
  • boolean add(T e)：将元素加入队列，功能与 offer 相同。
• 参数说明：
  • e: 需要加入队列的元素。
• 返回值：boolean，返回 true 表示元素成功加入队列，false 表示元素被丢弃。
• 作用：用于动态维护队列的前 N 名元素，当队列超出容量时自动丢弃优先级低的元素。
• 实际开发场景：在处理分布式数据时，可以通过多次 offer 操作，从多个来源合并前 N 名数据。

2.3 转换为 List

BoundedPriorityQueue 支持将当前队列转换为 List，以便进一步操作。

示例：将队列转换为列表

import cn.hutool.core.collection.BoundedPriorityQueue;
import java.util.List;

public class BoundedPriorityQueueExample {
    public static void main(String[] args) {
        // 创建一个容量为 5 的有界优先队列
        BoundedPriorityQueue<Integer> queue = new BoundedPriorityQueue<>(5);

        // 添加元素
        int[] array = new int[]{5, 7, 9, 2, 3, 8};
        for (int i : array) {
            queue.offer(i);
        }

        // 将队列转换为列表
        List<Integer> list = queue.toList();

        // 打印列表结果
        System.out.println("转换为列表后的结果: " + list);
    }
}

• 方法签名：List<T> toList()
• 参数说明：无参数。
• 返回值：List<T>，返回当前队列中的元素列表。
• 作用：将优先队列转换为 List，便于进行排序、遍历等操作。
• 实际开发场景：在获取到前 N 名数据后，可以将队列转换为列表进行进一步处理或输出。

3. 实际应用场景

• 多源数据合并排序：在分布式系统中，处理来自多个数据源的结果并取出前 N 名。
• 大规模数据筛选：在处理大数据时，通过 BoundedPriorityQueue 高效筛选出符合条件的前 N 名数据，减少内存消耗。
• 实时流式计算：在流式数据处理中，通过有界优先队列实时维护最重要的前 N 名元素。