Java: PriorityQueue should not be iterated

Rules and Languages New rules / language support
1

Description

java.util.PriorityQueue and java.util.concurrent.PriorityBlockingQueue are designed to give out items via poll() in a specific order according to a given Comparator. However the used data structure under the hood to achieve the sorting in an optimized way is a heap structure which is not fully sorted and only does a partial sort on offer() and poll() to ensure the next polled element is indeed the minimal element according to the Comparator.
Iterating the PriorityQueue with an Iterator on the other hand iterates the underlying heap in the current order and thus do not give the desired order in general so one is required to use poll() to get the elements in the correct order.
I suggest creating a new rule when using the aforementioned two classes with the following methods/structures:

  • forEach(Consumer<? super E>)
  • iterator()
  • spliterator()
  • for(E e : priorityQueue)

Noncompliant code

void iterate() {
    PriorityQueue<Integer> queue = new PriorityQueue<>();
    queue.offer(5);
    queue.offer(1);
    queue.offer(4);

    queue.iterator(); // Noncompliant
    queue.spliterator(); // Noncompliant
    queue.forEach(System.out::println); // Noncompliant; will print 1, 5, 4

    for (Integer value : queue) // Noncompliant
        System.out.println(value); // will print 1, 5, 4
}

Compliant Code

void iterate() {
    while (!queue.isEmpty()) // OK
        System.out.println(queue.poll()); // will print 1, 4, 5
}

Exceptions to the Noncompliant Code

Difficult to say. Maybe one should exclude logging purposes but mostly these are not handled with manual iteration either and could be difficult to spot.

External references

From the JavaDoc of the class PriorityQueue:

This class and its iterator implement all of the optional methods of the Collection and Iterator interfaces. The Iterator provided in method iterator() and the Spliterator provided in method spliterator() are not guaranteed to traverse the elements of the priority queue in any particular order. If you need ordered traversal, consider using Arrays.sort(pq.toArray()).

Type

Code Smell or Bug