Java PriorityQueue

PriorityQueue 是优先队列的实现。在本教程中，我们将通过示例了解 Java 集合框架的 PriorityQueue 类。

在本教程中，我们将通过示例了解 Java 集合框架的 PriorityQueue 类。

优先队列，不像先进先出的普通队列，优先队列赋予每个元素不同的优先级，按照优先级排序服务元素，优先级最高的元素位于队列的头部，优先级最低的元素位于队列的尾部，优先级最高的元素最先出队列。优先队列，通常采用堆数据结构来实现。

PriorityQueue 类实现了 Queue 接口，拥有队列的常规操作。

Java PriorityQueue 类实现了 Queue 接口。

创建优先队列

为了创建优先队列，我们必须先导入 java.util.PriorityQueue 类，再按照如下方式创建对象：

PriorityQueue<Integer> numbers = new PriorityQueue<>();

在这里，我们创建了一个没有任何参数的优先级队列。默认情况下，优先级队列的头部是队列中自然排序最小的元素。也就是说默认的优先队列是以元素的默认升序排序定义优先级的。

PriorityQueue 的方法

PriorityQueue 类实现 Queue 接口， Queue 接口中定义的所有方法都可用在 PriorityQueue 类上。

将元素插入 PriorityQueue

  • add() - 将指定的元素插入队列。如果队列已满，则抛出异常。
  • offer() - 将指定的元素插入队列。如果队列已满，则返回 false 。

例如，

import java.util.PriorityQueue;

public class Main {
  public static void main(String[] args) {
    // 创建优先队列
    PriorityQueue<Integer> numbers = new PriorityQueue<>();

    // 使用 add() 添加元素
    numbers.add(4);
    numbers.add(2);
    System.out.println("PriorityQueue: " + numbers);

    // 使用 offer() 添加元素
    numbers.offer(1);
    System.out.println("Updated PriorityQueue: " + numbers);
  }
}

输出

PriorityQueue: [2, 4]
Updated PriorityQueue: [1, 4, 2]

在这里，我们创建了一个名为 numbers 的优先级队列，并且将 4 和 2 插入了队列。

虽然在 2 之前插入了 4，但是队列的头是 2，因为默认情况下优先级队列的头是队列中最小的元素。

然后我们将 1 插入到队列中，队列现在的头部元素是优先级最高的 1 。

访问 PriorityQueue 元素

peek() 方法此方法返回队列的头部元素。例如，

import java.util.PriorityQueue;

public class Main {
  public static void main(String[] args) {
    // 闯将优先队列
    PriorityQueue<Integer> numbers = new PriorityQueue<>();
    numbers.add(4);
    numbers.add(2);
    numbers.add(1);
    System.out.println("PriorityQueue: " + numbers);

    // 使用 peek() 获取头部元素
    int number = numbers.peek();
    System.out.println("Accessed Element: " + number);
  }
}

输出

PriorityQueue: [1, 4, 2]
Accessed Element: 1

删除 PriorityQueue 元素

  • remove(obj) - 从队列中删除指定的元素
  • remove() - 删除并返回队列的头部，如果不存在抛出异常
  • poll() - 删除并返回队列的头部元素，如果不存在返回 null

例如，

import java.util.PriorityQueue;

public class Main {
  public static void main(String[] args) {
    // 创建优先队列
    PriorityQueue<Integer> numbers = new PriorityQueue<>();
    numbers.add(4);
    numbers.add(2);
    numbers.add(1);
    System.out.println("PriorityQueue: " + numbers);

    // 使用 remove() 方法
    boolean result = numbers.remove(2);
    System.out.println("Is the element 2 removed? " + result);

    // 使用 poll() 方法
    int number = numbers.poll();
    System.out.println("Removed Element Using poll(): " + number);
  }
}

输出

PriorityQueue: [1, 4, 2]
Is the element 2 removed? true
Removed Element Using poll(): 1

迭代优先队列

要迭代优先级队列的元素有 2 中方法：

  1. 使用 iterator() 方法返回的迭代器对象，利用迭代器对象迭代队列
  2. 使用 forEach() 方法迭

看下面的实例：

import java.util.PriorityQueue;
import java.util.Iterator;

public class Main {
  public static void main(String[] args) {

    // 创建优先队列
    PriorityQueue<Integer> numbers = new PriorityQueue<>();
    numbers.add(4);
    numbers.add(2);
    numbers.add(1);

    // 使用 iterator() 方法
    System.out.print("PriorityQueue using iterator(): ");
    Iterator<Integer> iterate = numbers.iterator();
    while (iterate.hasNext()) {
      System.out.print(iterate.next() + ", ");
    }

    System.out.println();
    // 使用 forEach() 方法
    System.out.print("PriorityQueue using forEach(): ");
    numbers.forEach(item -> System.out.print(item + ", "));
  }
}

输出

PriorityQueue using iterator(): 1, 4, 2,
PriorityQueue using forEach(): 1, 4, 2,

其他 PriorityQueue 方法

方法 说明
contains(element) 检查队列中是否包含指定的元素，找到返回 true ，否则返回 false 。
size() 返回优先队列的长度。
toArray() 将优先级队列转换为数组并返回。

优先队列比较器

在上面的所有示例中，优先级队列元素的优先级是按自然顺序（升序）定义的。但是，我们可以自定义元素的优先级。

为此，我们需要通过实现 Comparator 接口创建自己的比较器。例如：

import java.util.PriorityQueue;
import java.util.Comparator;

public class Main {
  public static void main(String[] args) {
    // 创建优先队列
    PriorityQueue<Integer> numbers = new PriorityQueue<>(new CustomComparator());
    numbers.add(4);
    numbers.add(2);
    numbers.add(1);
    numbers.add(3);
    System.out.print("PriorityQueue: " + numbers);
  }
}

// 自定义比较器
class CustomComparator implements Comparator<Integer> {
  @Override
  public int compare(Integer number1, Integer number2) {
    // 以自然排序相反的顺序排列
    return number1.compareTo(number2) * -1;
  }
}

输出

PriorityQueue: [4, 3, 1, 2]

在上面的例子中，我们创建了一个优先队列，并在构造方法中使用自定义比较器对象作为参数。

关于自定义比较器的说明：

  • 自定义比较器需要实现 Comparator 接口
  • compare(a, b) 方法需要传入每次参与比较的 2 个参数，返回值需满足下列条件：
    • 如果 a > b 返回大于 0 的整数
    • 如果 a < b 返回小于 0 的整数
    • 如果 a = b 返回 0

实现自定义比较器的方法除了采用上面示例中新建一个类实现 Comparator 接口外，还可以采用匿名类和 lambda 表达式，这两种方式能让代码更简洁。如下：

  • 匿名类

    Comparator<Integer> myComparator =
    new Comparator<Integer>() {
      @Override
      public int compare(Integer number1, Integer number2) {
        return number1.compareTo(number2) * -1;
      }
    };

PriorityQueue<Integer> numbers = new PriorityQueue<>(myComparator);

  • lambda 表达式

    Comparator<Integer> myComparator = (number1, number2) -> number1.compareTo(number2) * -1;
PriorityQueue<Integer> numbers = new PriorityQueue<>(myComparator);
Java Queue 接口 Java Deque 接口