PriorityQueue clarification in Java

Question

In the below code, I want to know the significance of 10 while creating a PrioriyQueue. I know its the initial capacity but will it affect performance??

import java.util.*;

class Test {
    static class PQsort implements Comparator<Integer> { // inverse sort
        public int compare(Integer one, Integer two) {
            return two - one; // unboxing
        }
    }

    public static void main(String[] args) {
        int[] ia = { 1, 5, 3, 7, 6, 9, 8 }; // unordered data
        PriorityQueue<Integer> pq1 = new PriorityQueue<Integer>(); // use
                                                                    // natural
                                                                    // order
        for (int x : ia)
            pq1.offer(x);
        for (int x : ia)
            // review queue
            System.out.print(pq1.poll() + " ");
        System.out.println("");
        PQsort pqs = new PQsort(); // get a Comparator
        PriorityQueue<Integer> pq2 = new PriorityQueue<Integer>(10, pqs); // use
                                                                            // Comparator
        for (int x : ia)
            // load queue
            pq2.offer(x);
        System.out.println("size " + pq2.size());
        System.out.println("peek " + pq2.peek());
        System.out.println("size " + pq2.size());
        System.out.println("poll " + pq2.poll());
        System.out.println("size " + pq2.size());
        for (int x : ia)
            // review queue
            System.out.print(pq2.poll() + " ");
    }
}

Did you consider reading the Javadoc before you posted? Instead of posting? — user207421, May 23 '12 at 10:18

score 1 · Accepted Answer · answered May 23 '12 at 07:37

Javadoc explains:

A priority queue is unbounded, but has an internal capacity governing the size of an array used to store the elements on the queue. It is always at least as large as the queue size. As elements are added to a priority queue, its capacity grows automatically. The details of the growth policy are not specified.

In other words, being able to specify the initial capacity is a way to optimize performance if one discovers that the queue spends too much time growing its internal array.

You may have the same question for ArrayList (and some other collections): http://stackoverflow.com/questions/3564837/capacity-of-arraylist — Jean Logeart, May 23 '12 at 07:39

score 0 · Answer 2 · answered May 23 '12 at 07:40

The API docs do explain what the capacity is. It's the size of the internal array.

http://download.java.net/jdk7/archive/b123/docs/api/java/util/PriorityQueue.html

Allowing you to specify an initial capacity is a small optimization. 
If you know how many entries you will need, you can save the (tiny) time 
spent growing the queue to the required size, by sizing it correctly 
from the start.

PriorityQueue clarification in Java

2 Answers2