Default size of priority queue in java

2.5k views Asked by At

I am wondering why the default size of a PriorityQueue in Java is 11. I looked up the implementation and it made things more confusingly for me.

The priority queue is implemented as a heap. Its capacity is adjusted using this function:

/**
 * Increases the capacity of the array.
 *
 * @param minCapacity the desired minimum capacity
 */
private void grow(int minCapacity) {
    if (minCapacity < 0) // overflow
        throw new OutOfMemoryError();
    int oldCapacity = queue.length;
    // Double size if small; else grow by 50%
    int newCapacity = ((oldCapacity < 64)?
                       ((oldCapacity + 1) * 2):
                       ((oldCapacity / 2) * 3));
    if (newCapacity < 0) // overflow
        newCapacity = Integer.MAX_VALUE;
    if (newCapacity < minCapacity)
        newCapacity = minCapacity;
    queue = Arrays.copyOf(queue, newCapacity);
}

I don't understand the initial value 11 for the capacity. I think that the capacity should always be 2 to the number of levels. Any clarification?

1

There are 1 answers

1
JB Nizet On BEST ANSWER

11 is probably a number that was chosen more or less arbitrarily, as a trade off between memory consumption (a too large number would consume too much memory for nothing), and CPU consumption (a too low number would need too many resizes of the queue). And they probably benchmarked typical use cases to choose this number and the strategy used to resize the queue.