Внутреннее устройство PriorityQueue PriorityQueue — это реали | Библиотека джависта | Java, Spring, Maven, Hibernate
Внутреннее устройство PriorityQueue
PriorityQueue — это реализация интерфейса Queue на основе двоичной кучи. Элементы всегда упорядочены по приоритету, минимальный элемент всегда в голове.
Базовая структура
PriorityQueue использует min-heap реализацию:
public class PriorityQueue {
transient Object[] queue; // массив-куча
private int size = 0;
private final Comparator comparator;
private static final int DEFAULT_INITIAL_CAPACITY = 11;
}
Главные особенности:
→ O(log n) для add и poll (вставка/удаление с перестройкой).
→ O(1) для peek (доступ к минимуму).
→ O(n) для remove(Object) и contains.
→ Не гарантирует полную сортировку, только min в голове.
→ Не потокобезопасна (для concurrent используйте PriorityBlockingQueue).
Как устроено хранение
Binary Heap — complete binary tree в массиве
PriorityQueue с элементами: [2, 5, 8, 9, 12, 10, 15]
Куча (min-heap):
2
/ \
5 8
/ \ / \
9 12 10 15
Массив queue[]:
[2, 5, 8, 9, 12, 10, 15]
0 1 2 3 4 5 6
Индексация:
- Родитель узла i: (i - 1) / 2
- Левый ребёнок узла i: 2 * i + 1
- Правый ребёнок узла i: 2 * i + 2
Свойство min-heap:
Каждый родитель ≤ своих детей. Это НЕ полная сортировка — только гарантия минимума в корне.
Операции добавления и удаления
add(E element) / offer(E element) — добавление
1. Элемент добавляется в конец массива: queue[size++] = element.
2. Вызывается siftUp(size-1) для восстановления heap property:
— Элемент "всплывает" вверх, пока не станет больше родителя.
— Сравнения через Comparator или Comparable.
Алгоритм siftUp:
void siftUp(int k) {
E x = queue[k];
while (k > 0) {
int parent = (k - 1) >>> 1; // деление на 2
E e = queue[parent];
if (compare(x, e) >= 0) break;
queue[k] = e; // родитель опускается
k = parent; // поднимаемся выше
}
queue[k] = x; // вставляем элемент
}
Сложность: O(log n) — высота дерева.
poll() — удаление минимального элемента
1. Сохраняется минимум: E result = queue[0].
2. Последний элемент перемещается в корень: queue[0] = queue[--size].
3. Вызывается siftDown(0) для восстановления heap:
— Элемент "тонет" вниз, меняясь с меньшим ребёнком.
Алгоритм siftDown:
void siftDown(int k) {
E x = queue[k];
int half = size >>> 1; // size / 2
while (k < half) {
int child = (k << 1) + 1; // левый ребёнок
E c = queue[child];
int right = child + 1;
if (right < size && compare(c, queue[right]) > 0) {
child = right; // правый меньше
c = queue[child];
}
if (compare(x, c) <= 0) break;
queue[k] = c; // ребёнок поднимается
k = child; // опускаемся ниже
}
queue[k] = x;
}
Сложность: O(log n).
peek() — доступ к минимуму
E peek() {
return (size == 0) ? null : (E) queue[0];
}
Сложность: O(1) — прямой доступ к корню.
contains(Object o) — проверка наличия
1. Линейный поиск по массиву queue[].
2. Сравнение через equals().
Сложность: O(n) — требуется обход массива.
remove(Object o) — удаление элемента
1. Линейный поиск элемента: O(n).
2. Удаление найденного:
— Перемещение последнего элемента на место удаляемого.
— siftDown() или siftUp() для восстановления heap.
Сложность: O(n) поиск + O(log n) восстановление = O(n).
Важные нюансы
Comparator vs Comparable
Элементы должны быть сравниваемыми. Без Comparator/Comparable → ClassCastException.
НЕ полностью отсортирована
Heap гарантирует только минимум в корне.
Iterator не гарантирует порядок
Для sorted iteration используйте poll() в цикле:
Null элементы НЕ допускаются
Подходит
— Нужен доступ к минимуму/максимуму
— Динамическая сортировка
— Алгоритмы с приоритетами
— Top K проблема
Документация: JavaDoc (Java 17)
Ставьте , если хотите ещё разбор.
══════ Навигация ══════
Вакансии • Задачи • Собесы
Библиотека джависта
#CoreJava
