На этом шаге мы рассмотрим использование этого класса для создания очередей с приоритетом.
Данная реализация двоичной кучи обычно подкрепляется обыкновенным списком, и она поддерживает вставку и извлечение наименьшего элемента за O(log n) время.
См. документацию Python "heapq": https://docs.python.org/3.6/library/heapq.html.
Этот модуль - хороший выбор для реализации очередей с приоритетом в Python. Поскольку двоичная куча heapq технически обеспечивает только реализацию min-heap (то есть кучи, где значение в любой вершине не больше, чем значения ее потомков), должны быть предприняты дополнительные шаги, которые обеспечат стабильность сортировки и другие функциональные возможности, которые, как правило, ожидают от "практической версии" очереди с приоритетом.
См. документацию Python "Примечания к реализации очереди с приоритетом": https://docs.python.org/3.6/library/heapq.html.
>>> import heapq >>> q = [] >>> heapq.heappush(q, (2, 'программировать')) >>> heapq.heappush(q, (1, 'есть')) >>> heapq.heappush(q, (3, 'спать')) >>> while q: next_item = heapq.heappop(q) print(next_item) # Результат: (1, 'есть') (2, 'программировать') (3, 'спать')
На следующем шаге мы рассмотрим класс queue.PriorityQueue.
