Как устройство PriorityQueue определяет сложность проверки наличия произвольного элемента?
Проверка наличия произвольного элемента через PriorityQueue.contains имеет линейную сложность O(n). Куча гарантирует порядок только между родителем и его детьми, поэтому при поиске по значению нельзя надёжно отбросить целые поддеревья.
Очереди с приоритетом появились для задач, где нужно быстро получать элемент с наивысшим или наименьшим приоритетом: планирования работ, обработки событий и алгоритмов на графах. Для этого не требуется полностью сортировать все элементы после каждой операции.
PriorityQueue использует структуру кучи, которая обеспечивает быстрый доступ к корневому элементу и поддерживает порядок при добавлении и извлечении. Цена этой оптимизации — отсутствие эффективного поиска произвольного значения.
Разработчик может ожидать, что раз элементы упорядочены по приоритету, операция contains тоже будет логарифмической. Это неверно: наличие элемента определяется сравнением с конкретным объектом, а не только его приоритетом.
Если часто вызывать contains на большой очереди, каждая проверка может просматривать значительную часть массива кучи. В цикле это способно привести к суммарной сложности порядка O(n²) и заметному падению производительности.
В куче выполняется локальный инвариант: приоритет родителя не хуже приоритета его потомков. Например, у минимальной кучи каждый родитель меньше либо равен детям. Однако элементы в разных ветвях не обязаны быть упорядочены относительно друг друга.
Поэтому при поиске объекта с помощью contains реализация должна последовательно проверять элементы. Максимальная сложность — O(n); сравнение выполняется по равенству объектов, а не по тому, где объект должен находиться согласно компаратору.
Это отличается от операций над вершиной кучи:
Компаратор не превращает поиск в бинарный. Даже если он задаёт строгий порядок, массив кучи не является отсортированным массивом, поэтому двоичный поиск по нему неприменим.
В планировщике задач нужно добавлять задания по приоритету и не допускать повторной постановки одной и той же задачи. Вариант с вызовом contains перед каждым добавлением прост, но при росте очереди приводит к повторным линейным проходам и может сделать обработку большой пачки задач квадратичной.
Можно заменить очередь на TreeSet, получив поиск за O(log n), но это изменит семантику: элементы будут уникальны согласно компаратору, а задачи с одинаковым приоритетом могут считаться одинаковыми. Кроме того, структура уже не будет обычной очередью с произвольными дубликатами.
Практичное решение — хранить очередь приоритетов отдельно, а идентификаторы активных задач дублировать в HashSet. Проверка уникальности выполняется в среднем за O(1), а получение следующей задачи сохраняет сложность O(log n). Нужно поддерживать обе структуры согласованно, особенно при отмене и завершении задач; это дополнительная цена за нужную производительность.
Нет. Компаратор участвует в поддержании порядка кучи и выборе элемента для вершины, но contains ищет конкретный объект. Для такого поиска недостаточно знать отношения приоритетов между родителями и детьми, поэтому линейный просмотр сохраняется.
poll удаляет корневой элемент. После перемещения последнего элемента на его место достаточно просеять его вверх или вниз по одной цепочке кучи, длина которой пропорциональна высоте дерева, то есть O(log n). Удаление произвольного объекта сначала должно найти его за O(n), и только затем может потребоваться восстановление свойства кучи.
Очередь приоритетов оптимизирована для выбора следующего элемента, а не для проверки ключей уникальности. Наличие одинаковой задачи по идентификатору требует отдельной индексной структуры, например HashSet. При этом идентификатор должен иметь корректные equals и hashCode, а удаление или завершение задачи должно обновлять и множество идентификаторов, и очередь.