Учебники

Python — Кучи

Декабрь 19, 2018

Куча — это особая древовидная структура, в которой каждый родительский узел меньше или равен своему дочернему узлу. Тогда это называется Min Heap. Если каждый родительский узел больше или равен своему дочернему узлу, он называется максимальной кучей. Это очень полезно при реализации приоритетных очередей, где элементу очереди с более высоким весом предоставляется больший приоритет при обработке. Подробное обсуждение кучи доступно на нашем сайте здесь. Пожалуйста, сначала изучите его, если вы новичок в структуре данных. В этой главе мы увидим реализацию структуры данных кучи с использованием Python.

Создать кучу

Куча создается с помощью встроенной библиотеки Python с именем heapq. Эта библиотека имеет соответствующие функции для выполнения различных операций над структурой данных кучи. Ниже приведен список этих функций.

  • heapify — эта функция преобразует обычный список в кучу. В результирующей куче наименьший элемент помещается в позицию индекса 0. Но остальные элементы данных не обязательно сортируются.
  • heappush — эта функция добавляет элемент в кучу без изменения текущей кучи.
  • heappop — эта функция возвращает наименьший элемент данных из кучи.
  • heapreplace — эта функция заменяет самый маленький элемент данных новым значением, предоставленным в функции.

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

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

import heapq

H = [21,1,45,78,3,5]
# Use heapify to rearrange the elements
heapq.heapify(H)
print(H)

Когда приведенный выше код выполняется, он дает следующий результат — 

[1, 3, 5, 78, 21, 45]

Вставка в кучу

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

import heapq
H = [21,1,45,78,3,5]
# Covert to a heap
heapq.heapify(H)
print(H)
# Add element
heapq.heappush(H,8)
print(H)

Когда приведенный выше код выполняется, он дает следующий результат — 

[1, 3, 5, 78, 21, 45]
[1, 3, 5, 78, 21, 45, 8]

Удаление из кучи

Вы можете удалить элемент с первого индекса, используя эту функцию. В приведенном ниже примере функция всегда удаляет элемент в позиции индекса 1. 

import heapq

H = [21,1,45,78,3,5]
# Create the heap

heapq.heapify(H)
print(H)

# Remove element from the heap
heapq.heappop(H)

print(H)

Когда приведенный выше код выполняется, он дает следующий результат — 

[1, 3, 5, 78, 21, 45]
[3, 21, 5, 78, 45]

Замена в куче

Функция heapreplace всегда удаляет наименьший элемент кучи и вставляет новый входящий элемент в какое-то место, не зафиксированное ни в каком порядке.

87
Share: