Список приоритетов с сортировкой кучи (Java)

Question

Я хотел бы знать, если существует собственная реализация Java для списка приоритетов, используя подход сортировки кучи. Если нет, есть ли рекомендуемая альтернатива?

Answer 1

Javadoc для PriorityQueue говорит:

"Неограниченная приоритетная очередь, основанная на куче приоритетов".

И у исходного кода PriorityQueue для (Java 6 и далее) есть этот комментарий:

"Очередь приоритетов представлена ​​в виде сбалансированной двоичной кучи..."

Технически говоря, это не Heapsort. Однако стандартный алгоритм Heapsort не подходит для очереди с приоритетами: он неинкрементный (O(NlogN)). Какие PriorityQueue do является инкрементным (O(logN) для вставки в очередь).

Для более подробной информации читайте исходный код. Это хорошо прокомментировано.