优先队列PriorityQueue＜＞ (a, b) -＞ b - a详细介绍

Dear 丶 2023-09-25 00:01 124阅读 0赞

# 1.介绍 #

`PriorityQueue` 是 Java 中的一个`队列实现`，是`一种基于优先级堆（Priority Heap）的数据结构`。它可以用于实现一些基于优先级的算法和应用，例如 Dijkstra 算法、A\*算法等等。

在这里，我们创建了一个 PriorityQueue 对象 maxHeap，并传入了一个`比较器对象 (a, b) -> b - a 作为参数`。这个比较器用于定`义元素之间的优先级，即元素大小的比较方式`。

`(a, b) -> b - a`表示将`两个元素 a 和 b 进行比较`

*  如果 `a 比 b 大，则返回一个负数`
 *  如果`a 比 b 小，则返回一个正数`
 *  如果 `a 和 b 相等，则返回 0`。
 *  这里我们将 b - a 作为返回值，表示我们`希望较大的元素在队列中具有较高的优先级`，也就是说，我们创建的是一个最大堆。

因此，通过 PriorityQueue 的实现，我们可以很方便地实现一个基于优先级的队列，将元素按照一定的顺序加入队列，并在取出元素时，`始终取出当前队列中优先级最高的元素`。

# 2.代码 #

public class Test {
        
        public static void main(String[] args) {
        
            // 创建一个最大堆，用于存储整数类型的数据
            PriorityQueue<Integer> maxHeap = new PriorityQueue<>((a, b) -> b - a);
    
    // 将一些数据加入堆中
            maxHeap.offer(3);
            maxHeap.offer(1);
            maxHeap.offer(4);
            maxHeap.offer(1);
            maxHeap.offer(5);
    
    // 不断取出优先级最高的元素，直到堆为空为止
            while (!maxHeap.isEmpty()) {
        
                int cur = maxHeap.poll();
                System.out.print(cur + " ");
            }
    
    // 输出：5 4 3 1 1
    
        }
    
    }

5 4 3 1 1

在上面的代码中，我们创建了一个最大堆 maxHeap，使用 PriorityQueue 类型的对象来实现。这里我们使用了一个`lambda 表达`式 (a, b) -> b - a 来定义元素的优先级顺序，其中 `b - a 表示较大的元素具有较高的优先级，即我们创建的是一个最大堆。`

我们将一些整数数据加入堆中，可以使用 offer() 方法向堆中添加元素，这里我们添加了 3、1、4、1、5 这五个整数。

然后我们使用`poll() 方法`来取出当前堆中优先级最高的元素，并打印输出。在本例中，我们不断取出堆顶元素，直到堆为空为止，输出的结果为：5 4 3 1 1。

在实际应用中，`最大堆`和`最小堆`都可以用来`实现优先队列`，具体使用哪一种取决于实际应用场景和需求。