# Priority Queues

Ash Gill
Ranch Hand
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
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.
Regards!

Ash Gill
Ranch Hand
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
Posts: 72
• 1
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
cheers Boris, got it. very informative reply, never knew about the iterator thing in PQ. thanks a lot.

Boris Mechkov
Ranch Hand
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
Posts: 37
My thought is: Since both LinkedList and PriorityQueue provide iterator() method, we can traverse a LinkedList as easily as a PriorityQueue.

Greenhorn
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.