Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Why PriorityQueue in Java cannot have initialCapacity 0?

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?

like image 248
Fixpoint Avatar asked Aug 31 '10 13:08

Fixpoint


2 Answers

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.

like image 100
chiccodoro Avatar answered Oct 09 '22 10:10

chiccodoro


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

like image 4
stark Avatar answered Oct 09 '22 09:10

stark