跳到主要内容

Java PriorityQueue

提示
  1. 优先队列的基本特性：Java中的PriorityQueue类提供了堆数据结构的功能，实现了队列接口，且元素按照排序顺序进行检索，不一定是排序的。
  2. 创建和使用PriorityQueue：通过导入java.util.PriorityQueue包可以创建优先队列。优先队列的头部是最小元素，可以使用Comparator接口自定义排序。
  3. PriorityQueue的主要方法：包括添加元素（add()和offer()）、访问元素（peek()）、移除元素（remove()和poll()），以及自定义比较器来改变元素排序方式。

在附图中，PriorityQueue类实现了队列接口，展示了PriorityQueue的结构和它与队列接口的关系。

PriorityQueue 类提供了 堆数据结构 的功能。

它实现了 队列接口。

Java PriorityQueue 类实现了队列接口。

与普通队列不同，优先队列的元素是按排序顺序检索的。

假设我们想按升序检索元素。在这种情况下，优先队列的头部将是最小的元素。一旦检索到这个元素，下一个最小的元素将成为队列的头部。

需要注意的是，优先队列的元素可能不是排序的。然而，元素总是按排序顺序被检索。

创建 PriorityQueue​

为了创建一个优先队列，我们必须导入 java.util.PriorityQueue 包。一旦我们导入了包，下面是在 Java 中创建优先队列的方式。

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

这里，我们创建了一个没有任何参数的优先队列。在这种情况下，优先队列的头部是队列中最小的元素。并且元素会按升序从队列中移除。

然而，我们可以借助 Comparator 接口来自定义元素的排序顺序。我们将在本教程后面学习这方面的内容。

PriorityQueue 的方法​

PriorityQueue 类提供了 Queue 接口中所有方法的实现。

向 PriorityQueue 插入元素​

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

例如，

import java.util.PriorityQueue;

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。

虽然 4 在 2 之前被插入，但队列的头部是 2。这是因为优先队列的头部是队列中最小的元素。

然后我们向队列中插入了 1。队列现在被重新排列，将最小的元素 1 存储到队列的头部。

访问 PriorityQueue 元素​

要从优先队列中访问元素，我们可以使用 peek() 方法。这个方法返回队列的头部。例如，

import java.util.PriorityQueue;

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() - 从队列中移除指定的元素
  • poll() - 返回并移除队列的头部

例如，

import java.util.PriorityQueue;

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]
元素 2 是否被移除？ true
使用 poll() 移除的元素： 1

遍历 PriorityQueue​

要遍历优先队列的元素，我们可以使用 iterator() 方法。要使用这个方法，我们必须导入 java.util.Iterator 包。例如，

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

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

        // 创建一个优先队列
        PriorityQueue<Integer> numbers = new PriorityQueue<>();
        numbers.add(4);
        numbers.add(2);
        numbers.add(1);
        System.out.print("使用 iterator() 遍历 PriorityQueue: ");

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

输出

使用 iterator() 遍历 PriorityQueue: 1, 4, 2,

PriorityQueue 的其他方法​

方法描述
contains(element)在优先队列中搜索指定的元素。如果找到了元素，返回 true；如果没有找到，返回 false。
size()返回优先队列的长度。
toArray()将优先队列转换为数组并返回。

PriorityQueue 的比较器​

在上面的所有示例中，优先队列元素都是按自然顺序（升序）检索的。然而，我们可以自定义这种排序。

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

import java.util.PriorityQueue;
import java.util.Comparator;
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) {
        int value =  number1.compareTo(number2);
        // 元素按倒序排序
        if (value > 0) {
            return -1;
        }
        else if (value < 0) {
            return 1;
        }
        else {
            return 0;
        }
    }
}

输出

PriorityQueue: [4, 3, 1, 2]

在上面的示例中，我们创建了一个传递了 CustomComparator 类作为参数的优先队列。

CustomComparator 类实现了 Comparator 接口。

然后我们重写了 compare() 方法。这个方法现在使队列头部的元素成为最大的数字。

要了解更多关于比较器的信息，请访问 Java Comparator。

最后于 更新