Кучи в Python

Изучение Python День 14

Куча — это специализированная древовидная структура данных, удовлетворяющая свойству кучи. В минимальной куче для любого заданного узла значение узла меньше или равно значениям его дочерних элементов. В максимальной куче значение любого узла больше или равно значениям его дочерних элементов.

Python предоставляет модуль heapq, который предоставляет функции для создания и управления кучами в своей стандартной библиотеке.

Создание кучи

Чтобы использовать кучи в Python, вам сначала нужно импортировать модуль heapq:

import heapq

Создание минимальной кучи

Чтобы создать мини-кучу, вы можете использовать функцию heapify() из модуля heapq. Эта функция преобразует список в допустимую кучу на месте:

heap = [4, 8, 2, 6, 7, 1]
heapq.heapify(heap)
print(heap)  # Output: [1, 6, 2, 8, 7, 4]

Вставка элементов

Вы можете добавить элементы в кучу, используя функцию heappush():

heap = [1, 4, 2, 7, 9]
heapq.heapify(heap)

heapq.heappush(heap, 5)
print(heap)  # Output: [1, 4, 2, 7, 9, 5]

Получение минимального элемента

Чтобы получить наименьший элемент из кучи (который всегда является корневым элементом), используйте функцию heappop():

min_value = heapq.heappop(heap)
print(min_value)  # Output: 1
print(heap)      # Output: [2, 4, 5, 7, 9]

Получение k самых больших элементов:

Вы можете использовать функцию nlargest(), чтобы получить k самых больших элементов из кучи:

heap = [1, 4, 2, 7, 9]
heapq.heapify(heap)

k_largest = heapq.nlargest(3, heap)
print(k_largest)  # Output: [9, 7, 4]

Получение k наименьших элементов

Точно так же вы можете использовать функцию nsmallest() для получения k наименьших элементов из кучи:

heap = [1, 4, 2, 7, 9]
heapq.heapify(heap)

k_smallest = heapq.nsmallest(3, heap)
print(k_smallest)  # Output: [1, 2, 4]

Сортировка кучей

Вы можете использовать модуль heapq для выполнения сортировки кучи в списке:

arr = [4, 2, 7, 1, 9, 3]
sorted_arr = []
for _ in range(len(arr)):
    sorted_arr.append(heapq.heappop(arr))
print(sorted_arr)  # Output: [1, 2, 3, 4, 7, 9]

Важная заметка

Помните, что heapq обеспечивает реализацию с минимальной кучей. Если вам нужна максимальная куча, вы можете инвертировать знак элементов в куче (например, использовать -value вместо value при добавлении элементов) или реализовать свои собственные функции сравнения.