Почему PriorityQueue в Java не может иметь initialCapacity 0?

Question

Я использую PriorityQueue для частичной сортировки некоторых данных. В частности, это код:

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

К сожалению, когда data collection пуста, код завершается ошибкой, потому что PriorityQueue не может быть передано ноль как initialCapacity. Каковы причины этого дизайнерского решения? Почему не может быть 0-размера PriorityQueue?

UPD: я знаю, как обойти это. Я хотел бы знать, почему PriorityQueue не включает в себя этот код max (1, n) - есть ли причины или это просто плохой дизайн API?

Answer 1

Почему вы хотите использовать очередь?Очередь - это структура данных, созданная для случая, когда у вас есть «производитель», который ставит в очередь элементы, и «потребитель», который их исключает.Приоритетная очередь упорядочивает элементы в очереди, используя древовидную структуру.Буфер необходим производителю для постановки в очередь, поэтому initialCapacity = 0 не имеет смысла.

В вашем случае вы никогда ничего не ставите в очередь, вы просто обрабатываете данныеиз коллекции у вас уже есть.Зачем создавать новую структуру данных для него?Вы можете просто использовать

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

или , следуя комментарию Даниэля, использовать Алгоритм выбора , чтобы вы могли извлечь выгоду из своей ситуации, что вам на самом деле нужно только подмножествоваши предметы.

Answer 2

Из исходного кода для 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.
*/

Подробнее: http://kickjava.com/src/java/util/PriorityQueue.java.htm#ixzz0yBp7ocHR

Answer 3

Есть другой конструктор , который можно использовать, чтобы избежать IllegalArgumentException.

public PriorityQueue(Collection<? extends E> c)

Первоначальная емкость очереди приоритета составляет 110% от размера указанной коллекции или1, если коллекция пуста.

Если вам нужен пользовательский компаратор, вы можете сделать вызов следующим образом (из ответа Джона):

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

Как уже говорили другие,не имеет смысла иметь очередь без емкости.Поскольку вы должны установить минимальную емкость где-то (вы, конечно, не хотите разрешать отрицательные значения), установка в 1 кажется разумной.

Answer 4

Если вы думаете, что означает емкость, это означает, что необходимо подготовить очередь для хранения по крайней мере X элементов без дополнительных выделений внутренней памяти.Таким образом, если вы ожидали, что очередь будет содержать не более 100 элементов, вы можете установить емкость 100 в конструкторе, чтобы подготовиться к этому.

Какой смысл указывать очереди ожидать НЕТ элементов?Не имеет смысла разрешать 0 в первую очередь, поэтому минимальное значение равно 1, и конструктор выдает исключение, если вы передаете 0 (или меньше).

Answer 5

Почему вы хотите создать коллекцию, но затем указать, что она должна быть пустой?

Вы можете просто создать экземпляр PriorityQueue с помощью Math.max(1, data.size())