Question

This question already has answers here:

Why does PriorityQueue.toString return the wrong element order? [duplicate] (4 answers)

Closed 7 years ago.

Short story, I m implementing a graph and now I m working on the Kruskal, I need a priority queue. My definition of a priority queue is that the element with the smallest key would come first? Is this wrong? Because when I insert the weighted edges(or numbers) in the queue they don t end up sorted.

PriorityQueue<Integer> tja = new PriorityQueue<Integer>(); 
tja.add(55);
tja.add(99); 
tja.add(1); 
tja.add(102);
tja.add(54);
tja.add(51);
System.out.println(tja);

That would print out this; [1, 54, 51, 102, 99, 55]. This is not sorted like I want them to be! And yes I made a comperator that goes into the priority queue that extracts the number from the edge object and compares based on that int. So this should work, or have I just completely misunderstood the entire concept of how this data structure works?

Answer 1

System.out.println is invoking the toString() method, which is using the iterator, which is not guaranteed to respect the natural ordering. From the docs: "The Iterator provided in method iterator() is not guaranteed to traverse the elements of the priority queue in any particular order."

Answer 2

I have no experience with PriorityQueue in Java but it looks like the priority thing is not integrated into iterator() or toString() (which uses iterator()).

If you do:

    while (tja.size()>0)
        System.out.println(tja.remove());

You get the proper results.

Answer 3

Are you familiar with functioning of Binary heaps? If not please go through min heap and max heap structures. PriorityQueue is implemented on heaps. PriorityQueue doesn t sort the items in increasing order, but it does the heap sort on it.

Go through the link: Priority Queue

The output you get is correct.

友情链接