The Built-In Iterator For Java'S Priorityqueue Does Not Traverse the Data Structure in Any Particular Order. Why

The built-in iterator for java's PriorityQueue does not traverse the data structure in any particular order. Why?

Because the underlying data structure doesn't support it. A binary heap is only partially ordered, with the smallest element at the root. When you remove that, the heap is reordered so that the next smallest element is at the root. There is no efficient ordered traversal algorithm so none is provided in Java.

PriorityQueue did not order its content correctly?

A priority queue gives no guarantee with regard to the ordering of the complete set; all it guarantees is that the smallest element is at the front (or the largest, if it's a max priority queue).

From the docs:

The Iterator provided in method iterator() is 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()).

Maybe to add a little context: what a priority queue does internally is store the elements in a tree structure of logarithmic height (in the sensible implementations using trees anyway). The insert and remove-like operations are designed to keep the smallest element at the root of that tree and to keep the elements in each subtree larger than the element of the parent vertex (that's what makes them heaps, that property is called the heap property). It does not guarantee any ordering on the elements of subtrees that are siblings as we know it for example from sort trees. The heap property together with the logarithmic height is what gives priority queues their fast operation runtimes, but it comes with the downside that you'll only ever get one element quickly, and that's the smallest one (or largest one for max heaps).

Why is this strange order happens in PriorityQueue in java?

PriorityQueue only guarantees that the first element is the smallest.

A binary heap only guarantees in each sub-heab (sub-tree) the root is the smallest element.

The heap is actually a complete-tree (or an array representation of it). Whenever you insert an element that violates the condition (is smaller then the root), the old root is sifted down. this is done recursively over the heap.

This partial ordering allows fast and relatively cache-efficient (with array representation) data structure that can be used if you only need the min element at each point at time.

Is iterator the best way to loop through PriorityQueue

If you want ordered retrieval of your elements, you must poll/remove elements from the queue; using iterator will not be enough.

PriorityQueue ordering issue

Your queue and the compareTo method are likely working correctly. Note what the API says about it:

This class and its iterator implement all of the optional methods of the Collection and Iterator interfaces. The Iterator provided in method iterator() is 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()).

The order is apparent when you retrieve items from the queue via the operations poll, remove, peek, and element.

Order of PriorityQueue not as expected

Let's have a look at PriorityQueue docs:

The Iterator provided in method iterator() is not guaranteed to traverse the elements of the priority queue in any particular order.

Same applies to Stream instances.

If you want to create a Stream instance that would traverse the queue in the order of priorities, you can do something like:

Stream.generate(queue::poll).limit(queue.size())

Keep in mind that polling will remove elements from the original queue.

How Java PriorityQueue sorting elements

You got it right but partially as you have missed the first part of it.

An unbounded priority queue based on a priority heap. The elements of the priority queue are ordered according to their natural ordering, or by a Comparator provided at queue construction time, depending on which constructor is used.

AS you can see it's clearly mentioned that it is based on priority heap. Now if you would like to understand what is Heap you can refer Binary Heap or in one line if you wanna understand basically there are 3 types of Heap -> Min & Map. Java's priority queue is using Min Heap, in this case

the key at root must be minimum among all keys present in Binary Heap and the same property must be recursively true for all nodes in the same tree

To implement this java use bit shifting also:

private static <T> void siftUpComparable(int k, T x, Object[] es) {
    Comparable key;
    int parent;
    for(key = (Comparable)x; k > 0; k = parent) {
        parent = k - 1 >>> 1;
        Object e = es[parent];
        if (key.compareTo(e) >= 0) {
            break;
        }

        es[k] = e;
    }

    es[k] = key;
}

PriorityQueue elements are not ordered

I've found that the problem is solved by getting elements via the poll() method which is similar to dequeue.

PriorityQueue<Edge> edges = new PriorityQueue<Edge>();
edges.add(new Edge(1, 2, 23));
edges.add(new Edge(2, 3, 1000));
edges.add(new Edge(1, 3, 43));

Edge temp;
while ((temp = edges.poll()) != null) 
 System.out.println(temp);

The reason this works is because poll() returns the head of the PriorityQueue, which is the least element, while an iterator just returns the elements the way they were added to the queue.

---

Related Topics