• 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
  • Tim Cooke
  • paul wheaton
  • Jeanne Boyarsky
  • Ron McLeod
Sheriffs:
  • Paul Clapham
  • Liutauras Vilda
  • Devaka Cooray
Saloon Keepers:
  • Tim Holloway
  • Roland Mueller
Bartenders:

Priority Queues

 
Ranch Hand
Posts: 71
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Hello guys, in one of the questions in K & B, i found this

It’s programmatically easier to perform a non-destructive traversal of a PriorityQueue
than a LinkedList. correct or incorrect?


and the answer was: is incorrect because the PriorityQueue class itself provides
no non-destructive traversal methods.


what do they mean by non-destructive traversal? if they mean traversing without removing objects then PriorityQueue does inherit peek() method which returns the highest priority element.
is the opposite of the statement correct i.e. "It’s programmatically easier to perform a non-destructive traversal of a linked list than a PriorityQueue"

many thanks and regards
 
Ranch Hand
Posts: 72
Netbeans IDE Tomcat Server Java
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

Ash Gill wrote:Hello guys, in one of the questions in K & B, i found this

It’s programmatically easier to perform a non-destructive traversal of a PriorityQueue
than a LinkedList. correct or incorrect?


and the answer was: is incorrect because the PriorityQueue class itself provides
no non-destructive traversal methods.


what do they mean by non-destructive traversal? if they mean traversing without removing objects then PriorityQueue does inherit peek() method which returns the highest priority element.
is the opposite of the statement correct i.e. "It’s programmatically easier to perform a non-destructive traversal of a linked list than a PriorityQueue"

many thanks and regards


Ash,
Think about it this way. Can you get two elements from a PriorityQueue without removing any? The answer is no. "Peek", "poll", "remove" and all other methods in the PriorityQueue API work on the element AT THE HEAD of the queue. This means you cant get to the second element (whatever that is, remember there is no order in the PQ) without removing the first one.
LinkedList has indexed access, meaning you can get a specific element at a specific index.

"It’s programmatically easier to perform a non-destructive traversal of a linked list than a PriorityQueue" - this statement is correct.
Hope all this answered your questions.
Regards!
 
Ash Gill
Ranch Hand
Posts: 71
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Hi Boris, thanks a lot for the reply. can you please explain a bit more on:

remember there is no order in the PQ



ques: priority queues are sorted and the order representes priorities of the elements. then arn't PQ ordered?

C

an you get two elements from a PriorityQueue without removing any? The answer is no. "Peek", "poll", "remove" and all other methods in the PriorityQueue API work on the element AT THE HEAD of the queue. This means you cant get to the second element (whatever that is, remember there is no order in the PQ) without removing the first one.
LinkedList has indexed access, meaning you can get a specific element at a specific index.



yes, i follow the above points but we can always traverse a PQ, without removing any element, using an Iterator and the Iterator can be used in the same way to traverse a LinkedList.
for eg:



ques: i understand that this is not same as getting to a particular element in a linkedlist using get(int index), but it is still a non-destructive traversal, isnt it?. please correct me.

thanks and regards
 
Boris Mechkov
Ranch Hand
Posts: 72
Netbeans IDE Tomcat Server Java
  • Likes 1
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

Ash Gill wrote:Hi Boris, thanks a lot for the reply. can you please explain a bit more on:

remember there is no order in the PQ



ques: priority queues are sorted and the order representes priorities of the elements. then arn't PQ ordered?

C

an you get two elements from a PriorityQueue without removing any? The answer is no. "Peek", "poll", "remove" and all other methods in the PriorityQueue API work on the element AT THE HEAD of the queue. This means you cant get to the second element (whatever that is, remember there is no order in the PQ) without removing the first one.
LinkedList has indexed access, meaning you can get a specific element at a specific index.



yes, i follow the above points but we can always traverse a PQ, without removing any element, using an Iterator and the Iterator can be used in the same way to traverse a LinkedList.
for eg:



ques: i understand that this is not same as getting to a particular element in a linkedlist using get(int index), but it is still a non-destructive traversal, isnt it?. please correct me.

thanks and regards



Sorry, i should have been more specific. Using the Iterator to traverse elements in a PQ does not guarantee order. Take a look at the PriorityQueue API

This class and its iterator implement all of the optional methods of the Collection and Iterator interfaces. 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()).

Because the original question was whether it was easier to implement a non-destructive traversal with PQ rather than LinkedLists, the answer would have been - LinkedList since you dont have to implement an Iterator.
 
Ash Gill
Ranch Hand
Posts: 71
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
cheers Boris, got it. very informative reply, never knew about the iterator thing in PQ. thanks a lot.
 
Boris Mechkov
Ranch Hand
Posts: 72
Netbeans IDE Tomcat Server Java
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

Ash Gill wrote:cheers Boris, got it. very informative reply, never knew about the iterator thing in PQ. thanks a lot.



No problem man!
 
Ranch Hand
Posts: 37
Eclipse IDE Java Linux
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
My thought is: Since both LinkedList and PriorityQueue provide iterator() method, we can traverse a LinkedList as easily as a PriorityQueue.
 
Greenhorn
Posts: 9
Android Oracle Java
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

Boris Mechkov wrote:

Ash Gill wrote:Hello guys, in one of the questions in K & B, i found this

It’s programmatically easier to perform a non-destructive traversal of a PriorityQueue
than a LinkedList. correct or incorrect?


and the answer was: is incorrect because the PriorityQueue class itself provides
no non-destructive traversal methods.


what do they mean by non-destructive traversal? if they mean traversing without removing objects then PriorityQueue does inherit peek() method which returns the highest priority element.
is the opposite of the statement correct i.e. "It’s programmatically easier to perform a non-destructive traversal of a linked list than a PriorityQueue"

many thanks and regards


Ash,
Think about it this way. Can you get two elements from a PriorityQueue without removing any? The answer is no. "Peek", "poll", "remove" and all other methods in the PriorityQueue API work on the element AT THE HEAD of the queue. This means you cant get to the second element (whatever that is, remember there is no order in the PQ) without removing the first one.
LinkedList has indexed access, meaning you can get a specific element at a specific index.

"It’s programmatically easier to perform a non-destructive traversal of a linked list than a PriorityQueue" - this statement is correct.
Hope all this answered your questions.
Regards!




this was really helpful, thank you
 
Mo-om! You're embarassing me! Can you just read a tiny ad like a normal person?
We need your help - Coderanch server fundraiser
https://coderanch.com/wiki/782867/Coderanch-server-fundraiser
reply
    Bookmark Topic Watch Topic
  • New Topic