• 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 ...
Marshals:
  • Campbell Ritchie
  • Jeanne Boyarsky
  • Ron McLeod
  • Paul Clapham
  • Liutauras Vilda
Sheriffs:
  • paul wheaton
  • Rob Spoor
  • Devaka Cooray
Saloon Keepers:
  • Stephan van Hulst
  • Tim Holloway
  • Carey Brown
  • Frits Walraven
  • Tim Moores
Bartenders:
  • Mikalai Zaikin

PriorityQueue poll() method

 
Ranch Hand
Posts: 176
3
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Hi,
I'm getting weird output after using poll() method. Technically it should just retrieve and delete the head but it's altering the queue in some way.
 
Marshal
Posts: 79254
377
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Please don't use // comments for anything at all long; the long lines are difficult to read. Don't use PriorityQueue as types for your variables and parameters; use Queue. Don't iterate the queue; use System.out.println(pq);
I am moving this discussion as too difficult for “beginning”.

I ran your code:-

java PriorityQueueDemo
1 10 2 10 11 12
Head of queue is 1
1 10 2 10 11 12
2 10 12 10 11
New Head of queue is 2

I fail to see what is wrong with that output; please explain what you expected to happen. The retrieval order of a priority queue is according to the natural ordering of its elements. When you remove the first element (1 takes precedence), the new smallest element (2) is brought to the head of the queue. This is what would have happened if your queue had not supported priorities:-

java PriorityQueueDemo
1 10 2 10 11 12
Head of queue is 1
1 10 2 10 11 12
10 2 10 11 12
New Head of queue is 10

I shall leave you to work out how I changed the code to get rid of the ordering; it was really simple.
 
Shubham Semwal
Ranch Hand
Posts: 176
3
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

Campbell Ritchie wrote:I shall leave you to work out how I changed the code to get rid of the ordering; it was really simple.



Got it
The Iterator provided in method iterator() is 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()).

Now I've just got to figure out how to implement it. Struggling with it atm.

I've another question "How to put priority in PriorityQueue elements ? On what basis it works differently than a normal queue ? When to implement it in a problem ?

 
Campbell Ritchie
Marshal
Posts: 79254
377
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Have you read the PriorityQueue documentation?
 
Saloon Keeper
Posts: 15543
364
  • Likes 1
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
A PriorityQueue uses a "binary min heap" as its internal data structure.

Binary heaps (not to be confused with heap memory) are data structures that are very efficient at sorting data, but sorting the data is 'destructive', meaning that returning the next element from the heap will necessarily remove it. That's why the iterator can't return the data in a sorted fashion, otherwise the heap would be empty at the end of the traversal.

Another consequence of using a heap is that the elements stored within it are repositioned in a 'weird' way when you remove the head. This is necessary to keep it working efficiently.

So why doesn't a PriorityQueue just sort all the elements to begin with? That's because this operation is very expensive if you have to repeat it every time you add a new element to the queue. Heaps are very fast at inserting elements.

A PriorityQueue is a very good type to remove elements with high priority, and inserting new elements needs to be fast. Usually a PriorityQueue is used for tasks that need to be processed by a pool of workers.
 
Shubham Semwal
Ranch Hand
Posts: 176
3
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Thanks @Stephan that was a very good answer
 
Shubham Semwal
Ranch Hand
Posts: 176
3
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

Campbell Ritchie wrote:Have you read the PriorityQueue documentation?


Yes. But I got very little out of it
 
reply
    Bookmark Topic Watch Topic
  • New Topic