|
Понятие кучи (heap). Модуль heapqКурс по стандартной библиотеке: https://stepik.org/a/259466?utm_source=proproprogs На этом занятии мы с вами познакомимся с функциями модуля heapq, которые позволяют эффективно отбирать минимальные и максимальные величины из последовательности данных. Но вначале немного теории, чтобы была ясна суть работы кучи (heap) в целом. Мы с вами рассмотрим работу двоичной кучи (heap), основанной на бинарном дереве. Как раз такая реализуется в модуле heapq. Давайте предположим, что изначально имеется некий пустой список: data = [] И в процессе работы программы в него постоянно то добавляются новые значения, то извлекаются существующие. Причем извлекать требуется одно или несколько наименьших величин. Это постановка задачи, в которой кучи (heap) показывают свою эффективность. Итак, предположим, что в программе необходимо последовательно добавить следующие значения в список data: 10, 5, 7, 16, 13, 2, 20 так, чтобы затем можно было бы быстро извлечь наименьшие величины. Для этого числа располагаются в виде бинарного дерева. Вначале поступает число 10. Оно размещается в корне дерева. Затем, второе число 5. Оно меньше 10, поэтому в корень ставится число 5, а число 10 в одну из дочерних вершин. Следующее число 7 меньше 5, поэтому размещается во втором потомке. Далее, идет число 16. Оно больше всех чисел в дереве и второй уровень дерева заполнен. Поэтому помещается в начало третьего уровня. Число 13 можно поставить на тот же уровень рядом с числом 16. Следующее число 2 меньше всех ранее добавленных. Следовательно, оно ставится в корень дерева, число 5 перемещается на второй уровень, а число 10 – на свободную позицию третьего уровня. Наконец, последнее наибольшее значение 20 просто добавляется в свободную позицию третьего уровня. В итоге получаем следующее бинарное дерево:
С последовательностью значений в списке data: data = [2, 5, 7, 16, 13, 10, 20] В результате полученное дерево обладает следующими двумя важными свойствами:
Такое дерево похоже на кучу, поэтому его и назвали heap, в данном случае имеем min-heap, т.к. минимальные значения располагаются сверху. По аналогии можно выстроить кучу max-heap, в которой максимальные значения располагаются сверху. В таком дереве (куче) легко находить минимальные значения. Достаточно выбирать их последовательно, начиная с корня. А при извлечении какого-либо минимального значения, быстро его перестраивать. В этом и состоит главная ценность такой структуры данных. Куча (heap) позволяет быстро извлекать минимальные (или максимальные) значения в постоянно меняющейся последовательности данных. Реализация кучи (heap) на PythonТак как куча (heap) – это стандартная и распространенная структура данных, то ее функционал уже реализован и доступен в модуле heapq: import heapq В самом простом варианте мы можем создать пустой список и с помощью функции heappush() добавлять в него последовательно произвольные числовые значения: d = [] heapq.heappush(d, 4) heapq.heappush(d, 1) heapq.heappush(d, 7) heapq.heappush(d, 5) Получим результат: [1, 4, 7, 5] Чтобы было понятно, как выглядит бинарное дерево, я написал простую функцию для его визуализации: def show_heap_tree(h): print('-- heap tree ----------------------------------------------------------') if len(h) <= 0: return fill = ' ' width = 32 lst_pos = {0: width} print(fill * width + str(h[0])) for i, x in enumerate(h): n = i + 1 ii, jj = 2 * i + 1, 2 * i + 2 lst_pos[ii] = lst_pos[i] - width // (n+1) lst_pos[jj] = lst_pos[i] + width // (n+1) if ii >= len(h): break elif jj >= len(h): print(fill * lst_pos[ii] + str(h[ii])) else: print(fill * lst_pos[ii] + str(h[ii]) + fill * 2 * (width // (n+1) - 1) + str(h[jj])) print('-- end heap tree ------------------------------------------------------') Вы можете не вникать в принцип ее работы, главное, что ей передается последовательность чисел, которая выводится в виде бинарного дерева. В частности для списка d: show_heap_tree(d) получим: --
heap tree ----------------------------------------------------------
Если же нужно построить кучу сразу по набору данных, то для этого существует функция heapify(), которая выполняется за линейное время O(n), где n – длина последовательности. Например: data = [10, 5, 7, 16, 13, 2, 20] heapq.heapify(data) print(data) show_heap_tree(data) Увидим в консоли: [2,
5, 7, 16, 13, 10, 20]
Наименьшее значение всегда будет располагаться в корне дерева, то есть по нулевому индексу списка d: min_value = data[0] # 2 Для извлечения минимального значения можно воспользоваться функцией heappop(): min_value = heapq.heappop(data) # 2 При этом список data изменится на следующий: [5, 13, 7, 16, 20, 10] Иногда нужно одновременно извлечь наименьший элемент и добавить новый. Это можно сделать одной функцией heapreplace(), которая заменяет первый элемент новым с переупорядочиванием кучи: min_value = heapq.heapreplace(data, 11) # 2 Итоговый список и дерево будут иметь вид: [5,
11, 7, 16, 13, 10, 20]
Аналогичная функция heappushpop() отличается от предыдущей heapreplace() тем, что если добавляемый элемент меньше корневого, то фактического добавления не происходит, т.к. он же сразу и извлекается. Например, команда: min_value = heapq.heappushpop(data, 1) # 1, data: [2, 5, 7, 16, 13, 10, 20] просто вернет 1 и никак не изменит кучу (бинарное дерево). А вот если прописать значение 3, которое больше корневого 2, то число 3 будет помещено в корень дерева, а число 2 возвратится функцией: min_value = heapq.heappushpop(data, 3) # 2, data: [3, 5, 7, 16, 13, 10, 20] Далее, для получения сразу k наименьших значений используется функция nsmallest() следующим образом: values = heapq.nsmallest(3, data) # values: [2, 5, 7] При этом список data никак не меняется, то есть, куча остается прежней. Аналогичная функция nlargest() возвращает k наибольших значений: values = heapq.nlargest(4, data) # values: [20, 16, 13, 10] Все эти методы работают за логарифмическое время O(log n), где n – длина последовательности. Пример использования кучи (heap) для реализации очереди с приоритетамиДавайте в заключении рассмотрим практический пример использования кучи для реализации очереди с приоритетами. На прошлом занятии мы с вами использовали для этой цели класс PriorityQueue модуля queue. Повторим его основной функционал, только без поддержки многопоточности. Используя модуль heapq, сделать это можно очень просто: class PriorityQueue: def __init__(self): self._queue = [] def put(self, item, priority): heapq.heappush(self._queue, (priority, item)) def get(self): return heapq.heappop(self._queue) В инициализаторе создается локальный атрибут _queue в виде пустого списка для хранения элементов очереди. Далее два метода. Первый метод put() добавляет элемент item в кучу типа min-heap. Причем делает это в виде кортежа, где первое значение – это приоритет, а второе – сами данные item. Второй метод get() возвращает элемент очереди с наименьшим приоритетом. Воспользоваться классом PriorityQueue можно следующим образом: pq = PriorityQueue() pq.put('Task A', 3) pq.put('Task B', 1) pq.put('Task C', 2) value = pq.get() print(value) # (1, 'Task B') В качестве домашнего задания добавьте в этот класс поддержку ограничения по длине очереди. Курс по стандартной библиотеке: https://stepik.org/a/259466?utm_source=proproprogs Видео по теме |
