🍧
Куча и очередь с приоритетомОчередь с приоритетом – это такая коллекция, которая поддерживает обязательно две следующие операции: вставка элемента с некоторым приоритетом (это может быть число или другой сравнимый объект) и извлечение элемента с наибольшим (или наименьшим приоритетом).
Очередь с приоритетом эффективно реализовать с помощью кучи.
Двоичная куча – бинарное дерево, где значение в любой вершине не меньше (больше), чем значения её потомков, при этом заполнение уровней должно быть последовательным (без дырок и перескоков на следующий уровень, если текущий уровень не закончен). Работа с кучей осуществляется за время порядка O(log n). А построение кучи из массива – за O(n), где n – число элементов.
Кучу удобно хранить в массивах. Напомню, что списки (list) в Python – это и есть массивы переменной длины, а не связные списки (linked list), как в других языках. Поэтому доступ к элементу по индексу осуществляется за O(1). Пускай в корень дерева мы положим наименьший элемент, а корнем дерева будет нулевой элемент списка
heap[0]
. Его потомками будут элементы
heap[1]
и
heap[2]
. В общем виде потомками элемента
heap[k]
будут
heap[2*k+1]
и
heap[2*k+2]
. Такая индексация позволяет хранить в массиве двоичное дерево компактно и удобно получать доступ к его элементам. По условиям кучи должны соблюдаться условия
heap[k] <= heap[2*k+1]
и
heap[k] <= heap[2*k+2]
.
В Python есть модуль
heapq, который предоставляет процедурный интерфейс по работе с двоичными кучами, причем его функции принимают в качестве кучи именно обычные объекты типа list.
Создать кучу можно двумя способами:
1) начать с пустого списка
[]
и заполнить его методом
heappush 2) взять существующий список и превратить его в кучу на месте (in-place) функцией
heapify.
heapify не возвращает новый список, а модифицирует переданный:
import heapq
x = [3, 1, 4, 2, 5]
heapq.heapify(x)
>>> x
[1, 2, 4, 3, 5]
Основные функции:
▶
heappush(heap, item) – добавляет в кучу элемент item.
▶
heappop(heap) - возвращает наименьший элемент и удаляет его из кучи. Если не надо удалять, то просто
heap[0]
.
▶ h
eappushpop(heap, item) – добавляет в кучу item, а после возвращает наименьший элемент (работает немного быстрее, чем в две операции).
▶
heapreplace(heap, item) – возвращает наименьший элемент, а потом уже добавляет новый item (работает немного быстрее, чем в две операции).
ℹ️ Помните! Отсортированный список является кучей – это лекго проверить по условиям. Поэтому если ваш массив заранее отсортирован, то не надо вызывать
heapq.heapify.
ℹ️ Но не любая куча – отсортированный список. Построение из массива – кучи, а из кучи – отсортированного массива – это сортировка кучей: мы наполняем последовательно кучу, а потом по порядку извлекаем наименьшие элементы, пока куча не истощится:
def heapsort(iterable):
h = []
for value in iterable:
heapq.heappush(h, value)
return [heapq.heappop(h) for i in range(len(h))]
>>> heapsort([1, 3, 5, 7, 9, 2, 4, 6, 8, 0])
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
В примерах выше, мы пользовались числами, как элементами кучи, потому что числа легко сравнимы. В реальной жизни мы оперируем произвольными объектами с их приоритетами. Для перехода от кучи к очереди с приоритетами можно использовать следующий трюк: использовать как элементы кортежи вида (приоритет, объект) или (приоритет, идентификатор, объект), если объекты несравнимы. Приоритет – число (например: важность задачи или время запуска какого-либо процесса). Идентификатором может служить порядковый номер.
q = []
heapq.heappush(q, (-priotiry, ident, obj))
ident += 1
Куча возвращает минимальный элемент (
heappop), а кортежи сравниваются поэлементно слева направо. Сначала идет
-priotiry. Знак минус, чтобы сначала возвращался не минимальный приоритет, а максимальный. Если приоритеты равны, то будет возвращен элемент с наименьшим идентификатором
ident, т.е. тот, что был добавлен раньше всех для данного значения приоритета.
Полный пример кода очереди с приоритетами
доступен по ссылке.