• Post Reply
  • Bookmark Topic Watch Topic
  • New Topic

Wrong output for PriorityQueue Implementation

 
luke brown
Ranch Hand
Posts: 31
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Posts: 3742
16
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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.
 
luke brown
Ranch Hand
Posts: 31
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Marshal
Pie
Posts: 21007
77
C++ Chrome Eclipse IDE Firefox Browser Java jQuery Linux VI Editor Windows
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
 
Stephan van Hulst
Bartender
Pie
Posts: 5590
55
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Pie
Posts: 5590
55
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Posts: 31
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Pie
Posts: 5590
55
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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:
 
  • Post Reply
  • Bookmark Topic Watch Topic
  • New Topic