1. Introduction

1.导言

One of the essential methods in PriorityQueue is the iterator() method. This method allows seamless traversal of the elements stored in the queue. In this tutorial, we’ll explore the iterator() method’s functionality and demonstrate its effective use in various scenarios.

PriorityQueueue 中的一个基本方法是 iterator() 方法。该方法允许无缝遍历队列中存储的元素。在本教程中，我们将探索 iterator() 方法的功能，并演示其在各种应用场景中的有效使用。

2. Overview of PriorityQueue

2.优先级队列概述

The PriorityQueue class in Java functions as a data structure, enabling the storage of elements in a queue based on their priority.

Java 中的 PriorityQueue 类作为一种数据结构，可根据元素的优先级将其存储在队列中。

PriorityQueue internally utilizes a binary heap, a tree-like structure where elements are arranged based on priority. The highest-priority element resides at the root, and child nodes inherit their parent’s priority. This arrangement ensures that the highest-priority element is positioned at the front while the lowest is placed at the back.

PriorityQueue 内部使用二进制堆，这是一种树状结构，其中的元素根据优先级排列。优先级最高的元素位于根节点，子节点继承父节点的优先级。这种安排确保了优先级最高的元素位于前端，而优先级最低的元素位于后端。

Additionally, the PriorityQueue class implements the Queue interface and offers a range of methods for manipulating the elements within the queue, including the iterator() method. The iterator() method is a part of the Iterable interface, and it is used to obtain an iterator over a collection of elements. The signature of the iterator() method is defined as:

此外，PriorityQueue 类实现了 Queue 接口，并提供了一系列用于操作队列中元素的方法，包括iterator() 方法。iterator() 方法是 Iterable 接口的一部分，用于获取元素集合的迭代器。iterator() 方法的签名定义如下：

public Iterator<E> iterator()

The iterator() method returns an Iterator over the elements in the queue. The type of parameter E specifies the type of elements in the queue. This method does not take any arguments

iterator() 方法返回队列中元素的迭代器。参数 E 的类型指定队列中元素的类型。该方法不带任何参数

3. Iterator Characteristics

3.迭代器特性

Let’s delve into the key characteristics of the iterator:

让我们深入了解迭代器的主要特征：

3.1. Fail-Fast Guarantee

3.1.快速故障保证

The iterator returned by the iterator() method is a fail-fast iterator. This means that if we attempt to modify the queue (add or remove elements) while an iterator is in use, a ConcurrentModificationException will be thrown. This behavior ensures that the iterator will always reflect the current state of the queue.

iterator() 方法返回的迭代器是fail-fast迭代器。这意味着，如果我们在使用迭代器时试图修改队列（添加或删除元素），将抛出 ConcurrentModificationException 异常。这种行为可确保迭代器始终反映队列的当前状态。

In the code, we modify the PriorityQueue by adding one more element after we obtain the iterator:

在代码中，我们通过在获得迭代器后添加一个元素来修改 PriorityQueueue ：</em

PriorityQueue<Integer> numbers = new PriorityQueue<>();
numbers.add(3);
numbers.add(1);
numbers.add(2);

Iterator<Integer> iterator = numbers.iterator();
numbers.add(4);

try {
    while (iterator.hasNext()) {
        System.out.println(iterator.next());
    }
} catch (ConcurrentModificationException e) {
    System.out.println("ConcurrentModificationException occurred during iteration.");
}

The output of this program will be:

该程序的输出结果将是

ConcurrentModificationException occurred during iteration.

3.2. Traversal Order

3.2.遍历顺序

The iterator() method traverses the heap structure in a specific way, often based on the level-order traversal method. This means it visits elements level by level, starting from the top of the heap and working its way down. This approach is efficient for accessing elements but might not always produce a strictly priority-based order.

iterator() 方法以特定方式遍历堆结构，通常基于层序遍历方法。这意味着它会逐级访问元素，从堆的顶层开始，然后一路向下。这种方法可以高效地访问元素，但并不总是能产生严格基于优先级的顺序。

Let’s look at an example of how to use the iterator() method to iterate over the elements in a PriorityQueue:

让我们来看一个示例，了解如何使用 iterator() 方法遍历 PriorityQueue 中的元素：

PriorityQueue<Integer> queue = new PriorityQueue<>();
queue.add(3);
queue.add(1);
queue.add(2);

Iterator<Integer> iterator = queue.iterator();
while (iterator.hasNext()) {
    Integer element = iterator.next();
    System.out.println(element);
}

In this example, we create a PriorityQueue of integers and add three elements to it. We then obtain an iterator over the elements in the queue and use a while loop to iterate over the elements, printing each one to the console. The output of this program will be:

在此示例中，我们创建了一个由整数组成的 PriorityQueueue 并向其中添加了三个元素。然后，我们获取队列中元素的迭代器，并使用 while 循环迭代元素，将每个元素打印到控制台。该程序的输出将是

1
3
2

Internally, the PriorityQueue looks like:

在内部，优先级队列看起来像这样：

   1
  / \
 3   2

During iteration, the iterator traverses the elements in level order, producing the order 1, 3, and 2. While this order maintains the general structure of the heap, it does not strictly adhere to the priority-based ordering.

在迭代过程中，迭代器按级别顺序遍历元素，产生 1、3 和 2 的顺序。虽然这种顺序保持了堆的一般结构，但并没有严格遵守基于优先级的排序。

4. Comparator Interface

4.比较器接口

In certain scenarios, we might want to order elements in the PriorityQueue based on a custom criterion. This can be achieved by utilizing the Comparator interface. This interface allows us to define a comparison function that can be used to order the elements in the queue.

在某些应用场景中，我们可能希望根据自定义标准对 PriorityQueue 中的元素进行排序。这可以通过使用 Comparator 接口来实现。该接口允许我们定义一个比较函数，用于对队列中的元素进行排序。

The Comparator interface has a single compare() method, which takes two arguments of the same type and returns an integer value. The value returned by the compare() method determines the ordering of the elements in the queue.

Comparator 接口有一个 compare() 方法，该方法接收两个相同类型的参数，并返回一个整数值。compare() 方法返回的值决定了队列中元素的排序。

Let’s consider the following example, where we have a Person class, and the requirement is to prioritize individuals based on their age. To address this, we’ll create a custom comparator:

让我们考虑下面的示例：我们有一个 Person 类，要求根据个人的年龄对其进行优先排序。为此，我们将创建一个自定义比较器：

class PersonAgeComparator implements Comparator<Person> {
    @Override
    public int compare(Person p1, Person p2) {
        return p1.age - p2.age; 
    }
}

Subsequently, we’ll create a PriorityQueue with custom ordering. We need to pass an instance of the PersonAgeComparator interface to the constructor of the PriorityQueue. The elements in the queue will then be ordered according to the comparison function defined by the Comparator:

随后，我们将创建一个具有自定义排序的 PriorityQueue 。我们需要将 PersonAgeComparator 接口的实例传递给 PriorityQueue 的构造函数。然后，队列中的元素将根据 Comparator 定义的比较函数进行排序：

PriorityQueue<Person> priorityQueue = new PriorityQueue<>(new PersonAgeComparator());

priorityQueue.add(new Person("Alice", 25));
priorityQueue.add(new Person("Bob", 30));
priorityQueue.add(new Person("Charlie", 22));

Iterator<Person> iterator = priorityQueue.iterator();

while (iterator.hasNext()) {
    Person person = iterator.next();
    System.out.println("Name: " + person.name + ", Age: " + person.age);
}

The output of this program will be:

该程序的输出结果将是

Name: Charlie, Age: 22
Name: Bob, Age: 30
Name: Alice, Age: 25

5. Ordered Retrieval

5.有序检索

The previous example didn’t display elements in strict ascending age order, even though we used a custom Comparator. The internal structure of PriorityQueue might lead to unexpected outcomes during direct iteration. This is because the iterator follows a level-order traversal, which results in a different sequence during iteration, as it visits elements level by level.

尽管我们使用了自定义比较器，但前面的示例并未按严格的年龄升序显示元素。在直接迭代过程中，PriorityQueue 的内部结构可能会导致意想不到的结果。这是因为迭代器遵循级别顺序遍历，在迭代过程中会产生不同的顺序，因为它会逐级访问元素。

To ensure elements are retrieved in the exact order of their priority, we can use the poll() method. This method specifically removes the element with the highest priority (in this case, the lowest age) from the PriorityQueue and returns it.

为确保按照优先级的确切顺序检索元素，我们可以使用 poll() 方法。该方法专门从 PriorityQueueue 中移除优先级最高的元素（在本例中为年龄最小的元素）并将其返回。

Let’s see how to use the poll() method to retrieve the element in ordering:

让我们看看如何使用 poll() 方法来检索排序元素：

while (!priorityQueue.isEmpty()) {
    Person person = priorityQueue.poll();
    System.out.println("Name: " + person.name + ", Age: " + person.age);
}

The output of this program will now be:

现在该程序的输出将是

Name: Charlie, Age: 22
Name: Alice, Age: 25
Name: Bob, Age: 30

6. Use Case

6.用例

Although iterator() might not be ideal for strictly-ordered retrieval, it excels in scenarios where the priority order isn’t crucial — for instance, capitalizing the person’s name in PriorityQueue or calculating statistics like average age, regardless of priority. Let’s illustrate the use case with an example:

虽然 iterator() 对于严格排序的检索可能并不理想，但它在优先级顺序并不重要的应用场景中却表现出色，例如，在 PriorityQueue 中将人名大写，或计算平均年龄等统计数据，而不考虑优先级。让我们举例说明该用例：

while (iterator.hasNext()) {
    Person person = iterator.next();
    person.setName(person.getName().toUpperCase());
}

7. Conclusion

7.结论

In this article, we’ve explored the PriorityQueue class in Java, emphasizing the role of the iterator() method. It’s important to note that while the PriorityQueue maintains sorted order internally, the iterator() method does not guarantee traversal in that order. Therefore, we use the iterator() method to perform operations that don’t rely on the priority order.

在本文中，我们探讨了 Java 中的 PriorityQueueue 类，并强调了 iterator() 方法的作用。值得注意的是，虽然 PriorityQueue 在内部保持排序顺序，但 iterator() 方法并不保证按此顺序遍历。因此，我们使用 iterator() 方法来执行不依赖优先级顺序的操作。

As always, the code is available over on GitHub.

与往常一样，代码可在 GitHub 上获取。