Куча — это разновидность графа, которую также называют очередью с приоритетами.
Очередь с приоритетами — это структура данных, куда можно добавлять элементы в любом порядке, а при извлечении они выбираются в зависимости от приоритета: от наименьшего к наибольшему (или наоборот). Каждый элемент в куче называется узлом. Узлы содержат данные.
Рассмотрим пример кучи. Каждый узел хранит число — элемент данных. Узлы связаны в древовидную структуру. Обычно у каждого узла не более двух потомков. Такое дерево называют бинарным.
Размер дерева зависит от объема данных.
Куча — это особый вид дерева, или графа. Есть правила, как хранить данные в куче. В максимальной куче (max heap) значения в родительских узлах всегда больше, чем в дочерних. В минимальной куче (min heap) — наоборот.
В min heap самое маленькое число всегда находится в корневом узле. Когда деревья хранятся в памяти, каждый новый ряд узлов идет правее предыдущего.
При извлечении числа из кучи убирается самый верхний элемент с минимальным значением. После этого структуру кучи нужно восстановить. Последний элемент в нижнем ряду (в данном случае — 6) поднимается наверх, становясь новым корневым узлом.
Если число в дочернем узле меньше, чем в родительском, заменим его на наименьшее из чисел в дочерних узлах. В данном случае число 6 в родительском узле больше, чем 5 в правом дочернем и 3 в левом. Поэтому левый дочерний узел и родитель поменяются местами. Продолжаем эту операцию, пока все узлы не станут упорядоченными. Например, если число 8 в правом дочернем узле окажется больше, чем 6 в родительском и 4 в левом, родитель и левый дочерний узел также поменяются местами.
В min heap всегда наименьший элемент находится в корне. Это позволяет извлекать его за константное время, независимо от общего объема данных. При перестройке кучи, после удаления минимального элемента, другие элементы перемещаются вверх, и дерево снова упорядочивается. Время, необходимое для перестройки, зависит от высоты дерева.
Если в куче n элементов, то ее высота не превышает log₂n. Это означает, что время на перестройку и добавление новых элементов составляет O(log n). Новые элементы поднимаются до тех пор, пока не выполнится условие кучи. Таким образом, время на добавление также пропорционально высоте дерева.
Модуль heapq
Модуль heapq входит в стандартную библиотеку Python. Он реализует низкоуровневые операции с кучей и некоторые общие высокоуровневые операции.
Основные операции:
heapify(iterable) - используется для преобразования итерации в структуру данных кучи.
heappush(heap, element) - используется для вставки элемента данных, указанного в его параметрах, в кучу.
heappop(heap) - используется для удаления и возврата наименьшего элемента данных из кучи.
heappushpop(heap, element) - используется для объединения операций push и pop в одном операторе, что приводит к повышению эффективности.
import heapq
# создаем список
numbers = [14, 23, 4, 43, 34, 9, 18, 1, 25, 8]
# превращаем список в кучу (min-heap)
heapq.heapify(numbers)
print("Куча после heapify:", numbers)
# добавляем элемент (вставка)
heapq.heappush(numbers, 20)
print("После добавления 20:", numbers)
# извлекаем минимальный элемент
smallest = heapq.heappop(numbers)
print("Извлеченный минимальный элемент:", smallest)
print("Куча после удаления:", numbers)
# вставка и извлечение за одну операцию
result = heapq.heappushpop(numbers, 7)
print("heappushpop (вставили 7, извлекли):", result)
print("Куча после heappushpop:", numbers)
# получаем 3 наименьших числа
three_smallest = heapq.nsmallest(3, numbers)
print("Три наименьших:", three_smallest)
# получаем 3 наибольших числа
three_largest = heapq.nlargest(3, numbers)
print("Три наибольших:", three_largest)Примерный вывод:
Куча после heapify: [1, 8, 4, 23, 14, 9, 18, 43, 25, 34]
После добавления 20: [1, 8, 4, 23, 14, 9, 18, 43, 25, 34, 20]
Извлеченный минимальный элемент: 1
Куча после удаления: [4, 8, 9, 23, 14, 20, 18, 43, 25, 34]
heappushpop (вставили 7, извлекли): 4
Куча после heappushpop: [7, 8, 9, 23, 14, 20, 18, 43, 25, 34]
Три наименьших: [7, 8, 9]
Три наибольших: [43, 34, 25]