Priority Queue to List. not adding properly

Question

I am trying to copy items out of a priority queue and into an ArrayList. for some reason, when there are three or four items, it stops after adding two items to the list. If there are 5 items, it stops after copying 3 items to the list. What am I doing wrong?

PriorityQueue<T> queue= new PriorityQueue<T> () ; 
List<T> list = new ArrayList<T>();

 for (int i = 0 ; i< queue.size(); i++)
        {
           list.add(0, queue.poll());
        }

Orcutt

Answer 1

Try the following code:

PriorityQueue<T> queue= new PriorityQueue<T> () ; 
List<T> list = new ArrayList<T>();

while(!queue.isEmpty()){
       list.add(0, queue.poll());
    }

An example:

import java.util.*;
import java.lang.*;
import java.io.*;

class Main{
    public static void main (String[] args) {
        PriorityQueue<Integer> queue = new PriorityQueue<>();
        queue.add(5);
        queue.add(4);
        queue.add(3);
        queue.add(2);
        queue.add(1);
        List<Integer> list = new ArrayList<>();
        while(!queue.isEmpty()) {
            list.add(0,queue.poll());
        }
        System.out.println(list);  // Prints [5, 4, 3, 2, 1]

    }
}

Why your for loop is not working:

Consider iteration 1: i = 0 and i <

queue.size() = 5 queue = {5,4,3,2,1} list = {}

After iteration 1:

queue = {5,4,3,2} list = {1} i = 1

At iteration 2: i = 1 i < queue.size() = 4 queue = {5,4,3,2} list = {1}

After iteration 2: queue = {5,4,3} list = {1,2} i = 2

At iteration 3: i = 2 i < queue.size() = 3 queue = {5,4,3,2} list = {1}

After iteration 3: queue = {5,4} list = {1,2,3} i = 3

At iteration 4: i = 3 i < queue.size() = 3? = > False

Quit the loop!

So you are quitting the for loop when still queue = {5,4} and all the elements are not added to list.

Steck

You might also add that the reason OP's loop is failing is due to queue.size() becoming smaller each iteration. Saving the end of loop would also have worked – Aalto

jontro, would you mind elaborating on that? I'm trying to figure out why my loop didn't work. What do you mean by saving the loop? – Orcutt

Oh I see what u mean. So my i is increasing, while my queue.size() is decreasing, so they meet in the middle. Insted, I should have saved the original queue.size() in a variable and used that? – Orcutt

You shouldn't have used i at all. You're not using it inside the loop. It's pointless. Just iterate while the queue isn't empty, as per this answer. – Playtime

That makes sense! Thanks EJP! – Orcutt

Answer 2

The reason is, the queue size is recalculated for each iteration but its size is reduced within the loop.

So, instead of calculating the queue size in the for loop... calculate it outside of the for loop. This way code does not need to recalculate it for each iteration and even though the queue size is reduced within the loop, it still iterates fully to the initial size of the list.

Some thing like:

PriorityQueue<T> queue= new PriorityQueue<T> () ; 
List<T> list = new ArrayList<T>();

int qSize = queue.size();

 for (int i = 0 ; i< qSize; i++)
 {
    list.add(0, queue.poll());
 }

Sonny

This doesn't provide anything better than the original answer. – Omsk

True... its just another way to solve the problem. – Sonny

Answer 3

ArrayList has a constructor that accepts Collection. PriorityQueue implements Collection. You don't need to iterate through queue.

PriorityQueue<T> queue= new PriorityQueue<T>();
List<T> list = new ArrayList<T>(queue);

Shinar

The PQ is only ordered as you remove from it. See the Javadoc. This will not work. – Playtime

This method works perfectly. And Javadocs doesn't say that it doesn't work. You can create ArrayList with all elements from the priority queue, though the order isn't specified. If this did not work, the queue would fail the contract of collection interface. – Shinar

That's what I said. Order is not preserved. The Javadoc says so here: 'The Iterator provided in method iterator() is not guaranteed to traverse the elements of the priority queue in any particular order.' – Playtime

The question was to copy elements from Priority Queue to ArrayList. This solution creates an ArrayList that contains all elements from PriorityQueue. There was no requirement to keep the order. – Shinar

Answer 4

you are polling elements, that means you are droping them from your queue, while you wanna iterate over it.

i would recommend you to use

queue.peek()

instead.

Keratoid

There's no way to iterate in a specific order. What I want to do is remove one at a time so that my ArrayList is ordered from largest to smallest. – Orcutt

queue won't work, because it can only access the root of the tree. I won't ever get the other elements. – Orcutt

btw the queue is ordered from largest to smallest, you don't need to reorder it – Keratoid

The PQ is only ordered as you remove from it. See the Javadoc. This will not work. – Playtime