Пост Очередь с приоритетом — это структура данных, которая поддерживает две операции: добавление элемента и извлечение минима…

Очередь с приоритетом — это структура данных, которая поддерживает две операции: добавление элемента и извлечение минимального из всех ранее добавленных элементов. Одной из самых распространённых реализаций очереди с приоритетом является бинарная куча. Это полное бинарное дерево со следующим свойством: ключ, хранящийся в каждом узле, меньше или равен (≤) ключам в дочерних узлах. Минимум всех элементов находится в корне такого дерева. 1 3 7 5 4 9 8 15 16 17 18 19 В бинарной куче сложность операций вставки и извлечения составляет O(log n). Обычный способ хранения полного бинарного дерева в памяти — это массив, где дочерние элементы для x[i] находятся в x[2*i+1] и x[2*i+2]. [1, 3, 7, 5, 4, 9, 8, 15, 16, 17, 18, 19] В Python нет бинарной кучи в виде класса, но предоставляется ряд функций, которые позволяют использовать список как бинарную кучу. Эти функции находятся в модуле heapq. In [1]: from heapq import * In [2]: heap = [3,2,1] In [3]: heapify(heap) In [4]: heap Out[4]: [1, 2, 3] In [5]: heappush(heap, 0) In [6]: heap Out[6]: [0, 1, 3, 2] In [7]: heappop(heap) Out[7]: 0 In [8]: heap Out[8]: [1, 2, 3] 📲 Мы в MAX 👉@BookPython