В очереди с приоритетом элементы выходят не по порядку поступления, а по приоритету: первым всегда наименьший. На этом держатся планировщики задач, Дейкстра и задачи "k наибольших". В уроке разберём ADT, три реализации и практическое использование heapq.
ADT: push и pop_min
ADT даёт три операции: push(priority, item), pop_min() (extract-min) и peek(). В отличие от обычной очереди, порядок выхода зависит не от времени поступления, а от приоритета. Чем меньше приоритет, тем важнее элемент; если нужен наибольший, меняем знак.
Три реализации
В неупорядоченном списке push за O(1), но pop_min сканирует список. В упорядоченном bisect.insort находит место за O(log n), но сдвиг элементов стоит O(n) (bisect). Двоичная куча снижает обе операции до O(log n): дерево хранится в массиве, родитель не больше детей, минимум лежит в h[0] (кучи).
