Java 优先队列

Java 优先队列

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

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

它实现了Queue接口。

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

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

需要注意的是，优先级队列的元素可能没有排序。但是，总是按排序顺序检索元素。

创建优先队列

为了创建优先级队列，我们​​必须导入 java.util.PriorityQueue 包裹。导入包后，下面是我们如何在 Java 中创建优先级队列。

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

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

但是，我们可以在 Comparator 的帮助下自定义元素的顺序 界面。我们将在本教程的后面部分了解这一点。

PriorityQueue的方法

PriorityQueue 类提供了 Queue 中所有方法的实现 界面。

将元素插入优先队列

• add() - 将指定元素插入队列。如果队列已满，则会引发异常。
• offer() - 将指定元素插入队列。如果队列已满，则返回 false .

例如，

import java.util.PriorityQueue;

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

        // Creating a priority queue
        PriorityQueue<Integer> numbers = new PriorityQueue<>();

        // Using the add() method
        numbers.add(4);
        numbers.add(2);
        System.out.println("PriorityQueue: " + numbers);

        // Using the offer() method
        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;

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

        // Creating a priority queue
        PriorityQueue<Integer> numbers = new PriorityQueue<>();
        numbers.add(4);
        numbers.add(2);
        numbers.add(1);
        System.out.println("PriorityQueue: " + numbers);

        // Using the peek() method
        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) {

        // Creating a priority queue
        PriorityQueue<Integer> numbers = new PriorityQueue<>();
        numbers.add(4);
        numbers.add(2);
        numbers.add(1);
        System.out.println("PriorityQueue: " + numbers);

        // Using the remove() method
        boolean result = numbers.remove(2);
        System.out.println("Is the element 2 removed? " + result);

        // Using the poll() method
        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

迭代优先队列

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

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

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

        // Creating a priority queue
        PriorityQueue<Integer> numbers = new PriorityQueue<>();
        numbers.add(4);
        numbers.add(2);
        numbers.add(1);
        System.out.print("PriorityQueue using iterator(): ");

        //Using the iterator() method
        Iterator<Integer> iterate = numbers.iterator();
        while(iterate.hasNext()) {
            System.out.print(iterate.next());
            System.out.print(", ");
        }
    }
}

输出

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

其他 PriorityQueue 方法

PriorityQueue 比较器

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

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

import java.util.PriorityQueue;
import java.util.Comparator;
class Main {
    public static void main(String[] args) {

        // Creating a priority queue
        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);
        // elements are sorted in reverse order
        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。