5

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?

Andrew Brēza
  • 7,705
  • 3
  • 34
  • 40
Algific
  • 1,470
  • 2
  • 18
  • 33
  • to get sorted layout you should use `while (!tja.isEmpty()){ System.out.println(tja.poll()); }` – serhii Jul 02 '15 at 21:51

3 Answers3

17

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."

omerkudat
  • 9,371
  • 4
  • 33
  • 42
7

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.

Grzegorz Oledzki
  • 23,614
  • 16
  • 68
  • 106
  • Perfect, so the structure is not sorted properly until you run remove. – Algific Nov 25 '09 at 09:03
  • 1
    No, the structure is always correctly sorted, just not when you are iterating over it. But if you call poll(), or peek(), or remove(), you get the elements in the correct order. – omerkudat Nov 25 '09 at 09:06
  • @data_hepp No. Remove doesn't sort the structure. The structure is already sorted but toString() or iterator() that it internally uses doesn't guarantee the traversal in order. – Varun Nov 25 '09 at 09:06
1

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.

Dixit Gokhale
  • 601
  • 1
  • 12
  • 32