• Post Reply Bookmark Topic Watch Topic
  • New Topic
programming forums Java Mobile Certification Databases Caching Books Engineering Micro Controllers OS Languages Paradigms IDEs Build Tools Frameworks Application Servers Open Source This Site Careers Other Pie Elite all forums
this forum made possible by our volunteer staff, including ...
  • Campbell Ritchie
  • Tim Cooke
  • Devaka Cooray
  • Ron McLeod
  • Jeanne Boyarsky
  • Liutauras Vilda
  • paul wheaton
  • Junilu Lacar
Saloon Keepers:
  • Tim Moores
  • Stephan van Hulst
  • Piet Souris
  • Carey Brown
  • Tim Holloway
  • Martijn Verburg
  • Frits Walraven
  • Himai Minh

Java PriorityQueue Order of elements

Posts: 10
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Hello everyone,
I have implemented an Dijkstra algorithm which uses an priority Q to save the currently proceeded nodes and an HashSet S which saves the settled nodes.
I try to understand the functioning and logged how the priority queue is modified.

Adding adjacent vertices to q
Adding adjacent vertices to q
Adding adjacent vertices to q
Current status2 of S: [e, d, a]
Current status2 of Q: [b, b, b, c]
Poll minimum vertex: b
Current status of S: [e, d, a]
Current status of Q: [b, c, b]

I do not understand, why after using the poll method on q, the order on the priority queue changes to [b,c,b], b has the smallest distnace and since it is a priority queue should
not it be [b,b,c] ?

S and Q contain my Node objects, and thats how I did overwrite the compareTo method:

Posts: 4334
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
It's hard to tell without seeing more code, but I think the problem is that when you print "Current status of S" and "Current status of Q", you're using PriorityQueue's toString() which is reallty AbstractCollection's toString(), which uses the Iterator to get the elements to be shown in the string.  But for a PriorityQueue we are told:

The Iterator provided in method iterator() and the Spliterator provided in method spliterator() are 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()).

What this means is, you can't rely on toString() to tell you what the priority-sorted order of the queue is.  It can tell you what's in the PriorityQueue, but not the proper sort order.  You can't really know that until you call poll() or peek().  Part of how PriorityQueue optimizes its operations is that it defers half the work of sorting until you actually retrieve something with poll().  

So what are your options?  One is to simply ignore the order you get from toString(), and only worry about whether you're getting the correct result when you call poll().  Another is, to print the sorted order, use something like this:

This is inefficient for large queues, but a good way to see what's going on for debugging purposes...
Listen. That's my theme music. That's how I know I'm a super hero. That, and this tiny ad told me:
the value of filler advertising in 2021
    Bookmark Topic Watch Topic
  • New Topic