Куча и очередь с приоритетом: кто в приёмном покое раньше
В обычной очереди обслуживают по порядку прихода. А в приёмном покое — по тяжести состояния. Структура, которая всегда мгновенно выдаёт «самого важного», называется кучей.
Иногда важен не порядок прихода, а степень важности — и тогда нужна структура, которая всегда держит «главного» под рукой.
Очередь с приоритетом отдаёт не того, кто пришёл первым, а того, кто важнее. Под капотом у неё — куча.
Зачем нужен приоритет
Представьте приёмный покой больницы. Пациенты приходят в случайном порядке, но врач должен брать не того, кто раньше зашёл, а того, кому хуже всех. Нужна структура, которая в любой момент мгновенно скажет: «вот самый тяжёлый» — и так же быстро примет новенького.
Это и есть очередь с приоритетом. Каждый элемент имеет вес (важность), и наружу всегда выдаётся элемент с наибольшим — или наименьшим — весом. А реализуют её через хитрую структуру под названием куча (heap).
Куча: дерево с правилом старшинства
Куча — это дерево, но с одним строгим законом: родитель всегда не важнее своих детей (в «мин-куче» — родитель всегда меньше детей). Это не полная сортировка: левый и правый ребёнок между собой не упорядочены. Гарантируется только одно — на самой вершине лежит минимум (или максимум). Именно его мы и хотим получать быстро.
Прелесть в том, что для ответа «кто главный?» не нужно ничего искать — главный всегда на верхушке. А вставка нового элемента и удаление верхушки занимают время O(log n): нужно лишь «протолкнуть» элемент вверх или вниз по высоте дерева, а высота растёт очень медленно — у миллиона элементов всего около двадцати уровней.
Как куча себя чинит
Положили новый элемент в самый низ — и он «всплывает»: пока он важнее родителя, меняется с ним местами, поднимаясь к своему уровню. Сняли верхушку — на её место ставим последний элемент и «топим» его вниз, меняя с более важным из детей, пока правило не восстановится. Несколько обменов по высоте — и порядок снова соблюдён.
Куча в действии
В Python куча встроена — это модуль heapq, работающий поверх обычного списка как мин-куча:
import heapq
# Пары (приоритет, имя). Чем меньше число — тем срочнее
pacients = []
heapq.heappush(pacients, (5, "лёгкий порез"))
heapq.heappush(pacients, (1, "остановка сердца"))
heapq.heappush(pacients, (3, "перелом"))
# Куча всегда отдаёт самого срочного
while pacients:
priority, name = heapq.heappop(pacients)
print(f"Зовём: {name} (приоритет {priority})")
Хотя «остановку сердца» добавили второй, она вышла первой: куча сама расставила пациентов по важности. Заметьте — мы ни разу не сортировали список целиком, и это ключ к скорости.
Где кучи работают по-настоящему
Очередь с приоритетом — рабочая лошадка многих алгоритмов. Знаменитый алгоритм Дейкстры, который ищет кратчайший путь в навигаторе, на каждом шаге берёт из кучи ближайший непосещённый перекрёсток. Планировщик задач в операционной системе выбирает процесс с наивысшим приоритетом. Система, которой нужно держать «топ-10» из потока миллионов чисел, хранит их в куче и почти не тратит память.
Куча против полной сортировки
Можно ведь просто сортировать список и брать первый элемент? Можно, но сортировка каждый раз заново — это дорого. Куча даёт золотую середину: она не тратит силы на полный порядок, а поддерживает ровно столько порядка, сколько нужно, чтобы верхушка всегда была правильной. За это её и любят.
Запомнить просто: куча — это структура, которая всегда держит «самого главного» наготове и быстро принимает новых, не упорядочивая всех остальных без надобности. Где есть приоритеты, там почти наверняка работает куча.