wood burning stoves 2.0*
The moose likes Programmer Certification (SCJP/OCPJP) and the fly likes Priority Queues Big Moose Saloon
  Search | Java FAQ | Recent Topics | Flagged Topics | Hot Topics | Zero Replies
Register / Login


Win a copy of Murach's Java Servlets and JSP this week in the Servlets forum!
JavaRanch » Java Forums » Certification » Programmer Certification (SCJP/OCPJP)
Bookmark "Priority Queues " Watch "Priority Queues " New topic
Author

Priority Queues

Ash Gill
Ranch Hand

Joined: Jun 30, 2011
Posts: 71
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
Boris Mechkov
Ranch Hand

Joined: May 13, 2011
Posts: 72

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!


OCPJP 6
Ash Gill
Ranch Hand

Joined: Jun 30, 2011
Posts: 71
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

Joined: May 13, 2011
Posts: 72

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

Joined: Jun 30, 2011
Posts: 71
cheers Boris, got it. very informative reply, never knew about the iterator thing in PQ. thanks a lot.
Boris Mechkov
Ranch Hand

Joined: May 13, 2011
Posts: 72

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


No problem man!
Jeffrey Tian
Ranch Hand

Joined: Jun 02, 2010
Posts: 34
My thought is: Since both LinkedList and PriorityQueue provide iterator() method, we can traverse a LinkedList as easily as a PriorityQueue.
Ahmed Adel
Greenhorn

Joined: Mar 29, 2013
Posts: 9

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
 
wood burning stoves
 
subject: Priority Queues
 
Similar Threads
Priority Queue and iterator
doubt priorityqueue
LinkedList and PriorityQueue doubt
preemptive scheduler
PriorityQueue