PriorityQueue elements are not ordered

Question

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?

You should check the docs, I have personally had to deal with 2 different implementations of `PriorityQueue` while using Java, one was min and the other was max. However, are you sure that using the `Iterator` reorders the `PriorityQueue`? — Alejandro, Apr 25 '14 at 09:58
@AlejandroLucena I'm pretty sure there's no max implementation in official java API's. To get max you just pass Collections.reverseOrder() to the PriorityQueue(int, Comparator) constructor. — jantristanmilan, Apr 25 '14 at 10:12
Yes, good point. I must have been confused. However, as the answers state below, the `Iterator` doesn't reorder the `PriorityQueue` — Alejandro, Apr 25 '14 at 10:55

score 1 · Answer 1 · answered Apr 25 '14 at 10:01

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 !!

score 0 · Answer 2 · answered Apr 25 '14 at 10:01

0

From JavaDoc:

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

answered Apr 25 '14 at 10:01

stridecolossus

1,449
10
24

score 0 · Accepted Answer · answered Apr 26 '14 at 06:17

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.

PriorityQueue elements are not ordered

3 Answers3