aspose file tools*
The moose likes Java in General and the fly likes Wrong output for PriorityQueue Implementation Big Moose Saloon
  Search | Java FAQ | Recent Topics | Flagged Topics | Hot Topics | Zero Replies
Register / Login
JavaRanch » Java Forums » Java » Java in General
Bookmark "Wrong output for PriorityQueue Implementation" Watch "Wrong output for PriorityQueue Implementation" New topic
Author

Wrong output for PriorityQueue Implementation

luke brown
Ranch Hand

Joined: May 15, 2014
Posts: 30
here is my PriorityQueue program to sort a customer class elements ...with an unexpectedly wrong output...please point out the bug.



here is the customer class




output not coming as per the sorted id:

Priority queue values are: [1------jay, 7------jim, 255------kim, 11------lie]
1------jay
7------jim
255------kim
11------lie


regards
Luke
Joanne Neal
Rancher

Joined: Aug 05, 2005
Posts: 3739
    
  16
It's not a bug, it's working as designed.
From the PriorityQueue.iterator javadoc
The iterator does not return the elements in any particular order.


Joanne
luke brown
Ranch Hand

Joined: May 15, 2014
Posts: 30
Joanne Neal wrote:It's not a bug, it's working as designed.
From the PriorityQueue.iterator javadoc
The iterator does not return the elements in any particular order.



yeah ..i got that ...it says that iterator doesn't return in any particular order...then how to obtain the arrangement as inside the queue.please let me know.

Regards
Luke
Henry Wong
author
Sheriff

Joined: Sep 28, 2004
Posts: 18981
    
  40

luke brown wrote:
yeah ..i got that ...it says that iterator doesn't return in any particular order...then how to obtain the arrangement as inside the queue.please let me know.


I don't think that the java.util.Queue interface provides an option to inspect the queue. You can only peek at the first element.

The java.util.Deque interface does provide such an iterator, but the PriorityQueue doesn't support that interface.

Henry


Books: Java Threads, 3rd Edition, Jini in a Nutshell, and Java Gems (contributor)
Stephan van Hulst
Bartender

Joined: Sep 20, 2010
Posts: 3649
    
  17

Internally, PriorityQueue is implemented as a min-heap, so the only guarantee that is made is that the first element is the smallest. After you remove the first element, the queue is re-heaped so that the next element is the smallest again. In order to retrieve elements in order, you have to keep removing the first element from the queue. You can do this using the poll() method.
Stephan van Hulst
Bartender

Joined: Sep 20, 2010
Posts: 3649
    
  17

You can also use the iterator, but then you'll have to call i.remove() after each call to i.next().
luke brown
Ranch Hand

Joined: May 15, 2014
Posts: 30
Stephan van Hulst wrote:You can also use the iterator, but then you'll have to call i.remove() after each call to i.next().


Thanks Steve...that post regarding min heap was quite informative...by the way the following code worked fine:

while(!prq.isEmpty())
{
System.out.println(prq.poll());
}

The point here is iterator scrambles the order in which the elements are stored in the priority queue. so either we can use peek or poll.

Thanks for your kind replies.

Regards
Luke.
Stephan van Hulst
Bartender

Joined: Sep 20, 2010
Posts: 3649
    
  17

The iterator doesn't scramble anything, it just shows the order in which the elements are stored internally. I didn't test it, but this should also work:
 
It is sorta covered in the JavaRanch Style Guide.
 
subject: Wrong output for PriorityQueue Implementation