Когда элементы упорядочены в PriorityQueues?

Question

Вставляет ли класс PriorityQueue приоритет приоритета элементов или просто, когда мы опрашиваем элемент только тогда, он находит элемент с наивысшим приоритетом и возвращает его?

Answer 1

Как уже упоминалось, классы PriorityQueue внутренне поддерживают двоичную кучу , и порядок элементов в этой куче определяется либо порядком по умолчанию, либо компаратором. Двоичная куча поддерживается в списке.

Ваш вопрос спрашивает, когда элементы заказаны. Когда вы добавляете элемент в очередь или удаляете элемент из очереди, порядок элементов перестраивается таким образом, чтобы элемент с наивысшим приоритетом находился в верхней части кучи: с индексом 0 в списке. Таким образом, ответ на ваш главный вопрос заключается в том, что PriorityQueue всегда знает, какой элемент имеет самый высокий приоритет. Это делает функцию peek() очень эффективной.

Порядок пунктов в остальной части списка немного сложнее. Остальная часть списка упорядочена , но не обязательно отсортирована . Порядок таков, что перестановка кучи после вставки или удаления эффективна. См. Вышеупомянутую статью о двоичных кучах для деталей об упорядочении кучи.

Answer 2

Из исходного кода самого JDK (мое форматирование):

Очередь приоритетов, представленная в виде сбалансированной двоичной кучи: два потомка queue[n] - это queue[2*n+1] и queue[2*(n+1)].

Очередь приоритетов упорядочивается по comparator или по естественному порядку элементов , если компаратор равен нулю : для каждого узла n в куче и каждый потомок d из n, n <= d. Элемент с наименьшим значением находится в queue[0], предполагая, что очередь не пуста.

Таким образом, вы можете рассматривать вставку / удаление элементов в PriorityQueue как операции, обеспечивающие результаты наряду с балансировкой кучи.