[FIXED] Java – PriorityQueue – Iterate respecting order without removing elements

Issue

Small question regarding Java priority queue please.

I am inserting bunch of digits inside a priority queue with an unsorted data set.

After all insertions, I expect the priority queue to be ordered, which is the case, so far so good.

Now, I need to "retrieve" (I am using retrieve here on purpose) the first N elements in order to sum them.

I need to do above line multiple time.

I went to try:

Approach 1:
The use of:

int sum = 0;
while(!priorityQueue.isEmpty() && N > 0) {
    sum = sum + priorityQueue.poll(); //tried also peek, remove, etc
}

This approach works great the first try. Things are ordered! But as the elements gets removed, the after first try will not yield a good result.

Approach 2:

int sum = 0;
Iterator<Integer> iterator = priorityQueue.iterator();
while (iterator.hasNext() && N > 0) {
sum = sum + iterator.next();

Big surprise here, the iterator next is unordered…

Summary:
approach 1 yields a result where I can iterate, and getting the correct priority order, but I am removing elements as I go.

approach 2 yields a result where I can iterate, elements remains, but the priority order is wrong.

Question:

How do I iterate over a priority queue, without removing the elements, while preserving the order please (and if possible, without allocating extra priority queues)

Thank you

Solution

You can’t.

A priority queue is not designed to be capable of doing this. It’s designed to optimize for its use case by not trying to sort the collection or make any subset of it accessible in sorted order — until elements get removed.

If you want a collection that can do that, you need a TreeSet, a sorted List, or some other fully sorted data structure.

Answered By – Louis Wasserman

Answer Checked By – Marie Seifert (Easybugfix Admin)

Leave a Reply

(*) Required, Your email will not be published