Better way to create an ordered array from priorityQueue in Java

Question

I can of course do the following:

        PriorityQueue<Integer> q = new PriorityQueue<Integer>(100, new Comparator<Integer>() {
            public int compare(Integer x, Integer y) {
                return Integer.valueOf(x).compareTo(y);
            }
        });
        ...//add some elements to q
        int[] arr = new int[q.size()];
        int i = 0;
        while (q.size() != 0) {
            arr[i++] = q.remove();
        }

But this approach emptied the queue which I want to keep. I know I could have sorted using that comparator (of course when it is not as trivial as above) to get this array, but I will have to create an array first, then copy elements from the queue to the array, then sort the array.

Is there any better approach? Thanks for your help!

Answer 1

From the Javadocs for PriorityQueue:

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()).

Create the array, then sort it. It's the prescribed way.

Answer 2

Can't you just empty a copy of the original queue?

PriorityQueue<Integer> temp = new PriorityQueue<Integer>( q );
int[] arr = new int[ q.size() ];

int i = 0;
while ( !temp.isEmpty() ) {
    arr[ i ] = temp.remove().intValue();
    i++;
}

Just as you did, but on a new queue. I think the cost of copying a priority queue is O(n). Or it should, at least. Emptying the queue is O(n log n), so the final cost is O(n log n), just as getting an array then sorting it.