Why PriorityQueue in Java cannot have initialCapacity 0?

Question

I use PriorityQueue for partial sorting of some data. In particular, this is the code:

Collection<Data> data = ...;
PriorityQueue<Data> queue = new PriorityQueue<Data>(data.size(), dataComparator);
queue.addAll(data);
// iterate over queue with remove() until we have as much data as we need or until queue is empty

Unfortunately, when data collection is empty, the code fails, because PriorityQueue cannot be passed zero as initialCapacity. What are reasons behind this design decision? Why can't there be an 0-sized PriorityQueue?

UPD: I know how to work around this. I'd like to know why doesn't PriorityQueue include this max(1, n) code inside it - are there any reasons or is it just a bad API design?

Answer 1

If you think want capacity means, it means preparing the queue to be able to store at least X items without requiring additional internal memory allocations. So if you expected a queue to contain a maximum of 100 items you might set capacity to 100 in the constructor to prepare for that.

What is the point of telling a queue to expect NO items? It doesn't make sense to allow 0 in the first place so the minimum value is 1 and the constructor throws an exception if you pass 0 (or less).

Answer 2

Why would you want to create a Collection but then specify that it should be empty?

You can just instantiate the PriorityQueue with Math.max(1, data.size())

Answer 3

There's another constructor you can use to avoid the IllegalArgumentException.

public PriorityQueue(Collection<? extends E> c)

The priority queue has an initial capacity of 110% of the size of the specified collection or 1 if the collection is empty.

If you need the custom comparator, you can make the call as follows (from Jon's answer):

PriorityQueue<Data> queue = new PriorityQueue<Data>(Math.max(data.size(), 1), dataComparator);

As others have said, it doesn't make much sense to have a queue with no capacity. Since you have to set the minimum capacity somewhere (you certainly don't want to allow negative values), setting it at 1 seems reasonable.

Answer 4

From the source code for PriorityQueue:

/**
* Priority queue represented as a balanced binary heap: the two children
* of queue[n] are queue[2*n] and queue[2*n + 1]. The priority queue is
* ordered by comparator, or by the elements' natural ordering, if
* comparator is null: For each node n in the heap and each descendant d
* of n, n <= d.
*
* The element with the lowest value is in queue[1], assuming the queue is
* nonempty. (A one-based array is used in preference to the traditional
* zero-based array to simplify parent and child calculations.)
*
* queue.length must be >= 2, even if size == 0.
*/

Read more: http://kickjava.com/src/java/util/PriorityQueue.java.htm#ixzz0yBp7ocHR

Answer 5

Why do you want to use a queue? A queue is a data structure made for the case where you have a "producer" which enqueues items, and a "consumer" which dequeues them. A priority queue orders the enqueued items using a tree structure. A buffer is needed for a producer being able to enqueue, so initialCapacity = 0 makes no sense.

In your case you never enqueue anything, you just process data from a collection you already have. Why create a new data structure for it? You could just use

for (Data item : Collections.sort(data, dataComparator)) {
    // ...
}

or, following Daniel's comment, use the Selection Algorithm so you can profit from your situation that you actually only need a subset of your items.