Что такое heap и как использовать эту структуру данных на Python Всем привет! В прошлом посте мы с вами разбирали очень крутой алгоритм сортировки, но как вы помните, не совсем был прост этот малый. Сегодня мы поговорим с вами про интересную структуру данных и ее использование на Python. Встречайте нашего героя - «heap» или «куча». Пост будет в двух частях, не забудьте про ваш теплый напиток или может уже холодненький, вроде уже теплеет. И так поехали:
Структура данных кучи представляет собой структуру данных на основе двоичного дерева, в которой каждый узел либо больше или равен (максимальная куча), либо меньше или равен (минимальная куча) своих дочерних элементов. В Python модуль «heapq» обеспечивает реализацию структуры данных кучи.
Вот пример того, как создать кучу в Python:
import heapq
heap = []
heapq.heappush(heap, 5)
heapq.heappush(heap, 3)
heapq.heappush(heap, 7)
heapq.heappush(heap, 1)
print(heap) # Вывод: [1, 3, 7, 5]
Функция «heappush» добавляет элемент в кучу и поддерживает свойство кучи. Наименьший элемент всегда находится в корне кучи.
Чтобы удалить наименьший элемент из кучи, вы можете использовать функцию «heappop»:
import heapq
heap = [1, 3, 7, 5]
smallest = heapq.heappop(heap)
print(smallest) # Вывод: 1
print(heap) # Вывод: [3, 5, 7]
В следующем посте мы поговорим с вами про временную сложность наших методов, а также разберем методы: «heapify», «heapreplace».
Ставьте ваши реакции на этот пост, если он вам понравился, также мы всегда рады вас услышать в комментариях.
Всем классного дня!
