Perché PriorityQueue in Java non può avere initialCapacity 0?

Question

Io uso PriorityQueue per l'ordinamento parziale di alcuni dati. In particolare, questo è il codice:

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 

Sfortunatamente, quando data raccolta è vuota, il codice non riesce, perché PriorityQueue non possono essere passati zero initialCapacity. Quali sono le ragioni alla base di questa decisione di progettazione? Perché non ci può essere un PriorityQueue dimensioni 0?

UPD: So come aggirare questo. Mi piacerebbe sapere perché lo PriorityQueue non include questo max (1, n) codice al suo interno - ci sono dei motivi o è solo una cattiva progettazione dell'API?

Answer 1

Perché si vuole utilizzare una coda? Una coda è una struttura dati creata per il caso in cui si ha un "produttore" che accoda gli oggetti e un "consumatore" che li rimuove. Una coda con priorità ordina gli elementi in coda usando una struttura ad albero. È necessario un buffer per consentire ad un produttore di accodare, quindi initialCapacity = 0 non ha senso.

Nel tuo caso sidati mai enqueue nulla, è solo di processo di una collezione che già avete. Perché creare una nuova struttura dati per questo?Si potrebbe utilizzare

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

o, dopo il commento di Daniel, utilizzare il Selection Algorithm in modo da poter trarre profitto dalla situazione che è in realtà solo bisogno di un sottoinsieme dei tuoi articoli.

Answer 2

Se pensate che voglia capacità significa, significa preparare la coda per essere in grado di memorizzare almeno X elementi senza richiedere ulteriori allocazioni di memoria interna. Pertanto, se si prevede che una coda contenga un massimo di 100 elementi, è possibile impostare la capacità su 100 nella funzione di costruzione per prepararla.

Qual è lo scopo di dire a una coda di aspettarsi NESSUN oggetto? Non ha senso consentire 0 in primo luogo, quindi il valore minimo è 1 e il costruttore genera un'eccezione se si passa 0 (o meno).

Answer 3

Perché si desidera creare una raccolta, ma specificare che dovrebbe essere vuota?

Si può solo un'istanza CodaConPriorita con Math.max(1, data.size())

Answer 4

C'è another constructor è possibile utilizzare per evitare l'IllegalArgumentException.

public PriorityQueue(Collection<? extends E> c) 

La coda di priorità ha una capacità iniziale di 110% della dimensione dell'insieme specificato o 1 se la raccolta è vuota.

Se è necessario il comparatore personalizzato, è possibile effettuare la chiamata come segue (dalla risposta di Jon):

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

Come altri hanno detto, non ha molto senso avere una coda con nessuna capacità. Dato che devi impostare la capacità minima da qualche parte (di certo non vuoi consentire valori negativi), impostarla su 1 sembra ragionevole.

Answer 5

Dal codice sorgente per CodaConPriorita:

/** 
* 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. 
*/ 

Per saperne di più: http://kickjava.com/src/java/util/PriorityQueue.java.htm#ixzz0yBp7ocHR