Во многих алгоритмах требуется искать в списке элемент с наивысшим приоритетом.
Для решения подобной задачи применяют
*очередь с приоритетами*.
Базовые операции для очереди с приоритетами:
Операция|Эффективность|Вызов
--|--|--
конструктор (пустой набор) |`O(1)`| ``std::priority_queue<int> s;``
количество и/или проверка на пустоту |`O(1)`| ``auto len=s.size();``\
``if(s.empty())...``
добавить значение |`O(log n)`| ``s.push(x);``
максимальное значение |`O(1)`| ``auto t=s.top();``
убрать максимальное |`O(log n)`| ``s.pop();``
Варианты реализации очереди с приоритетами:
* в STL через специальную структуру данных ["куча"](51057-4.html)
* на основе массива переменного или фиксированного размера
* на основе односвязного или двусвязного списка
В двух последних вариантах операция добавления будет выполняться за `O(n)` (поиск места для вставки и вставка в упорядоченную последовательность), а операции получения максимального и его удаления за `O(1)`.
Линейные АТД
Начало
Учебные материалы