¿Por qué PriorityQueue en Java no puede tener initialCapacity 0?

Question

Yo uso PriorityQueue para la clasificación parcial de algunos datos. En particular, este es el código:

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 

Por desgracia, cuando data colección está vacía, el código de falla, porque PriorityQueue no se puede pasar de cero como initialCapacity. ¿Cuáles son las razones detrás de esta decisión de diseño? ¿Por qué no puede haber un PriorityQueue de 0?

UPD: Sé cómo evitar esto. Me gustaría saber por qué PriorityQueue no incluye este código máximo (1, n). ¿Hay algún motivo o es solo un mal diseño de la API?

Answer 1

¿Por qué desea utilizar una cola? Una cola es una estructura de datos creada para el caso en el que tiene un "productor" que encola elementos, y un "consumidor" que los quita. Una cola de prioridad ordena los artículos en cola usando una estructura de árbol. Se necesita una memoria intermedia para que un productor pueda enrutar, por lo que initialCapacity = 0 no tiene sentido.

En su caso que datos nunca enqueue nada, sólo de proceso de una colección que ya tiene. ¿Por qué crear una nueva estructura de datos para ello?Se podía utilizar

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

o, siguiendo el comentario de Daniel, utilice el Selection Algorithm para que pueda beneficiarse de su situación que en realidad se necesita solamente un subconjunto de sus artículos.

Answer 2

Si cree que quiere capacidad significa, significa preparar la cola para poder almacenar al menos X elementos sin requerir asignaciones de memoria interna adicionales. Por lo tanto, si espera que una cola contenga un máximo de 100 elementos, puede establecer la capacidad en 100 en el constructor para prepararse para eso.

¿Cuál es el punto de decirle a una cola que NO se esperan artículos? No tiene sentido permitir 0 en primer lugar, por lo que el valor mínimo es 1 y el constructor arroja una excepción si pasa 0 (o menos).

Answer 3

¿Por qué querrías crear una Colección pero luego especificar que debería estar vacía?

justo Usted puede crear una instancia del PriorityQueue con Math.max(1, data.size())

Answer 4

Hay another constructor puede utilizar para evitar la IllegalArgumentException.

public PriorityQueue(Collection<? extends E> c) 

la cola de prioridad tiene una capacidad inicial de 110% del tamaño de la colección especificada o 1 si la colección está vacía.

Si necesita comparador personalizada, puede hacer la llamada de la siguiente manera (de la respuesta de Jon):

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

Como otros han dicho, no tiene mucho sentido tener una cola con sin capacidad Como tiene que establecer la capacidad mínima en algún lugar (sin duda no desea permitir valores negativos), establecerlo en 1 parece razonable.

Answer 5

A partir del código fuente para 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. 
*/ 

Leer más: http://kickjava.com/src/java/util/PriorityQueue.java.htm#ixzz0yBp7ocHR