Какая внутренняя организация позволяет std::priority_queue выполнять вставку за логарифмическое время?
std::priority_queue использует двоичную кучу, обычно размещённую в std::vector. При вставке новый элемент добавляется в конец базового контейнера, после чего поднимается вверх по куче; высота кучи равна O(log n). Просмотр наиболее приоритетного элемента выполняется за O(1), а удаление верхнего элемента — за O(log n).
STL строилась вокруг разделения алгоритмов, контейнеров и способов доступа к данным. Контейнерный адаптер позволяет предоставить специализированную структуру данных поверх уже существующего контейнера, не дублируя его управление памятью.
std::priority_queue решает задачу хранения элементов, когда важен быстрый доступ не к произвольной позиции, а только к элементу с наивысшим приоритетом. Для этого используется куча: она сохраняет необходимое отношение порядка, не требуя полностью сортировать все элементы.
Если поддерживать полностью отсортированную последовательность при каждой вставке, новая позиция может потребовать сдвига элементов или перестройки структуры. Вставка тогда будет стоить линейно либо логарифмически для поиска позиции плюс дополнительные расходы на изменение структуры.
Если же просто хранить элементы без специального инварианта, поиск максимального приоритета при каждом извлечении будет занимать O(n). Куча занимает промежуточную позицию: она поддерживает только частичный порядок, достаточный для быстрого доступа к вершине.
В двоичной куче каждый узел имеет не более двух потомков. Для максимальной кучи элемент в корне имеет наивысший приоритет, а каждый родитель не уступает своим детям по приоритету. Полной сортировки всех элементов при этом нет.
В std::priority_queue элементы хранятся в базовом контейнере, по умолчанию в std::vector. Логическая куча обычно представляется массивом: для позиции элемента вычисляются позиции родителя и потомков, поэтому отдельные указатели между узлами не нужны.
При вставке элемент помещается в конец массива. Затем выполняется просеивание вверх: элемент сравнивается с родителем и меняется с ним, пока инвариант кучи не будет восстановлен. Число таких шагов ограничено высотой дерева, то есть O(log n).
При удалении вершины последний элемент перемещается на её место и просеивается вниз. Это также требует не более O(log n) шагов. Операция top только обращается к корневому элементу и имеет сложность O(1).
Параметр сравнения задаёт приоритет косвенно. При стандартном сравнении std::less наверху оказывается наибольший элемент; в общем случае наверху находится элемент, который должен быть извлечён первым согласно заданному строгому слабому порядку.
Адаптер не предоставляет произвольный доступ к элементам, итераторы, удаление произвольного элемента или прямое изменение элемента внутри очереди. Это ограничение защищает инвариант кучи: изменение элемента без последующей перестройки могло бы сделать вершину не самой приоритетной.
В планировщике заданий требуется постоянно выбирать задачу с наивысшим приоритетом. Возможны три подхода.
Для сценария «добавить задачу и извлечь текущую самую приоритетную» выбирают std::priority_queue. Если задачи могут отменяться или их приоритеты часто меняются, применяют ленивое удаление с маркерами актуальности либо другую структуру, например упорядоченный контейнер; это увеличивает сложность реализации, но соответствует дополнительным операциям.
Нет, стандартный адаптер требует контейнер с возможностью эффективного обращения по индексу или эквивалентного произвольного доступа, поскольку операции кучи вычисляют позиции родителя и потомков. std::list предоставляет двунаправленные итераторы и не поддерживает произвольный доступ за константное время, поэтому он не подходит как базовый контейнер для std::priority_queue.
Построение из уже имеющегося диапазона может выполняться за O(n) с помощью линейной перестройки кучи. Это выгоднее, чем последовательное добавление всех элементов, которое в общем случае занимает O(n log n). Линейная оценка относится именно к построению всей кучи, а не к каждой отдельной вставке.
Адаптер не предоставляет операции изменения ключа или восстановления позиции произвольного элемента. Если объект был изменён так, что его приоритет изменился, структура может больше не удовлетворять инварианту кучи.
Обычно используют ленивое удаление: новую версию задачи помещают повторно, а при извлечении устаревшие записи пропускают. Если таких устаревших записей становится слишком много, очередь периодически перестраивают; альтернативой является контейнер или специализированная структура, поддерживающая изменение ключа напрямую.