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