PriorityQueue elements are not ordered [duplicate]

Question

This question already has answers here:

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

Closed 7 years ago.

Why isnt the output in ascending order?

public class Test {

    public static void main(String[] args) {
        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));

        Iterator<Edge> i = edges.iterator();
        while (i.hasNext())
            System.out.println(i.next());
    }


}

class Edge  implements Comparable<Edge> {
    private int v1;
    private int v2;
    private int w; 

    Edge(int v1, int v2, int w) {
        this.v1 = v1;
        this.v2 = v2;
        this.w = w;
    }

    public int getV1() {
        return v1;
    }


    public int getV2() {
        return v2;
    }

    public int getW() {
        return w;
    }

    @Override
    public int compareTo(Edge o) {
        return this.w - o.getW();
    }

    public String toString() {
        return ("v1: " + v1 + " v2: " + v2 + " w: " + w);
    }
}

I tried it using doing this using a List, and then calling Collections.sort(listToSort) and it works. I thought the head of the PriorityQueue is always the least element?

Answer 1

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.

Answer 2

From docs ,

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()).

Note that this implementation is not synchronized. Multiple threads should not access a PriorityQueue instance concurrently if any of the threads modifies the queue. Instead, use the thread-safe PriorityBlockingQueue class.

As @Alejandro Lucena stated , so try with toArray() method

Hope this helps !!

Answer 3

From JavaDoc:

Returns an iterator over the elements in this queue. The iterator does not return the elements in any particular order.