Куча в Питоне

В этой статье мы узнаем о важной структуре данных, куча в Python (известной как очередь кучи в Python). Мы узнаем о структуре данных и ее реализации, а затем посмотрите на код Python для того же.

Что такое кучи в Python?

Кучи в Python являются полными двоичными деревьями, в которых каждый узел либо меньше, чем равен или больше, чем равен всем своим детям (меньше или больше, в зависимости от того, является ли это макс-кучу или мин-куча).

Следовательно, корневой узел кучи – это либо самый маленький, либо самый большой элемент. Структура данных кучи обычно используется для представления очереди приоритета Отказ

Как правило, куча из двух форм:

Мин-куча : Min Heap – это куча, в которой все узлы меньше, чем их дети. Корень содержит самую низкую ценность в мин-куче.
Макс-куча : Макс куча – это куча, в которой все узлы больше, чем их дети. Корень содержит наибольшее значение в максимальной куче.

Ниже приведен пример для Min Heap и Max Heap.

Куча в Python, по умолчанию, мин-куча, а дальше в этой статье мы будем рассматривать мин-кучу, когда мы говорим о куче. Давайте теперь посмотрим, как структура данных кучи фактически реализована.

Как куча представлена в Python?

Структура данных кучи теоретически в форме бинарного дерева, но из-за его свойства полноты (в котором дерево завершено, за исключением правых узлов в последнем слое), куча хранится в форме массива в форме массива в объем памяти. Первый элемент содержит минимальный элемент (в случае min-heap).

Куча, которая находится в форме дерева, хранится в массиве, и его элементы проиндексируются следующим образом:

Корневой элемент будет в 0-й позиции массива, то есть куча [0].
Для любого другого узла, скажем, куча [I], у нас есть следующее:
- Родительский узел дан: куча [(I -1)/2].
- Левый узел дочернего ребенка дан: Heap [(2 * I) + 1]
- Правый узел дочернего ребенка дан: Куча [(2 * I) + 2]

Использование модуля HeaPQ для реализации кучи в Python

Python имеет модуль «Heapq» для реализации очереди кучи (или просто куча). Он содержит функциональные возможности, что наименьший элемент всегда будет в верхней части и будет выпущен при вызове функции POP.

Всякий раз, когда элементы либо толкнуты, либо выпущены, будет поддерживаться свойство кучи, а куча [0] всегда даст нам наименьшую функцию.

Модуль содержит следующие основные функции для кучи:

Хипифирование (iterable_name): Мы используем эту функцию для передачи любого намерения (например, список), и она преобразует его в структуру данных кучи.
Heapppush (Heapp_Name, Element_to_be_inserted): Как указано имя, эта функция нажимает/добавляет элемент в кучу. Нам нужно пройти имя и элемент кучи, чтобы быть вставленным в виде параметра. Функция заботится о перестановке кучи (если нужно), чтобы удовлетворить свойство кучи.
Heappop (HEAP_NAME): Как следует из названия, эта функция POPS/удаляет элемент из кучи, прошедшего в качестве параметра. Функция заботится о перестановке кучи (если нужно), чтобы удовлетворить свойство кучи.

Практическая реализация кучей Python

Теперь мы осуществим мин-кучу в Python. Мы используем Список [15, 7, 9, 4, 13] в коде и преобразуйте его в кучу, используя Хипифирование функция. Сделанная куча будет выглядеть так:

Реализация кучей в Python:

# The heap functionalities are in the heapq package, so import it
import heapq 
# we now initialise a list to be converted to heap 
lis = [15, 7, 9, 4, 13] 

# converting lis to heap using the heapify function
heapq.heapify(lis) 
print ("The heap looks like: ") 
print(lis)

#using the heappop function
print ("The popped item using heappushpop() is : ",end="") 
print (heapq.heappop(lis))

print ("After popping, the heap looks like: ")
print(lis)

#using the heappush function to push 2
print ("After pushing 2, the heap looks like: ") 
heapq.heappush(lis, 2) 
print(lis)

Выход:

The heap looks like: 
[4, 7, 9, 15, 13]
The popped item using heappop() is : 4
After popping, the heap looks like: 
[7, 13, 9, 15]
After pushing 2, the heap looks like: 
[2, 7, 9, 15, 13]

Здесь мы можем видеть, что пакет HeaPQ предоставляет функциональные возможности для создания очереди, и нажатием и поп-элементы. После нажатия или появления куча автоматически переставит себя, как видно на выходе.

Заключение

В этой статье мы узнали концепцию кучей в Python. Мы изучали, какие максимальные кучи и мин-куча в Python являются, и как они представлены.

Мы дополнительно реализовали его в Python, используя Хипифирование , Heapppush и Heappop Функции. Оставайтесь настроиться на более информативные статьи.

Счастливое обучение!