Приоритетная очередь
Очередь, где элементы извлекаются по приоритету, а не по порядку прихода.
Сигнатура
вставка/извлечение O(log n)Приоритетная очередь выдаёт не самый старый элемент, как обычная очередь, а элемент с наивысшим приоритетом. Чаще всего реализуется на двоичной куче. Лежит в основе Дейкстры, A* и кода Хаффмана.
Сложность: вставка и извлечение приоритетного элемента — O(log n); просмотр — O(1). Память: O(n).
import heapq
pq = []
heapq.heappush(pq, (2, "средний"))
heapq.heappush(pq, (1, "срочный"))
heapq.heappush(pq, (3, "низкий"))
print(heapq.heappop(pq)) # (1, 'срочный') — мин. приоритет первым