Модуль Python heapq: Использование heapq для создания очередей приоритетов в Python

Автор оригинала: Pankaj Kumar.

Привет всем! В сегодняшней статье мы рассмотрим использование модуля Python heapq.

Эти модули дают нам быстрый и простой способ создания любого типа приоритетной очереди для вашего приложения.

Чтобы понять больше об этом модуле, давайте рассмотрим его поближе.

Приоритетная очередь в виде минимальной кучи

Приоритетная очередь – это очередь, в которой элементы имеют другой параметр, называемый приоритетом. В зависимости от приоритета элемента эти элементы сначала выталкиваются/выскакивают из очереди.

Этот модуль использует двоичную минимальную кучу для построения очереди приоритетов.

Основное свойство этой структуры данных очереди кучи заключается в том, что самый маленький элемент всегда выскакивает первым!

Кроме того, как только какой-либо элемент выталкивается/выскакивает, сохраняется тот же тип структуры.

Эта структура данных имеет большое количество приложений, включая сортировку.

Давайте разберемся, как теперь мы можем использовать этот модуль.

Понимание модуля Python heapq

Этот модуль является частью стандартной библиотеки, поэтому нет необходимости устанавливать его отдельно с помощью pip .

Чтобы импортировать модуль heapq, мы можем сделать следующее:

import heapq

В модуле heapq нам в основном требуются 3 метода, которые нам нужны для построения и управления нашей приоритетной очередью:

• heappush(куча, элемент) -> Push item в кучу и сохранение свойства min-heap.
• heappop(куча) -> Выскакивает и возвращает самый маленький элемент из кучи. Если куча пуста, мы получим IndexError |/Исключение . heapify(iterable)
• -> Преобразует iterable (список и т. Д.) В минимальную кучу. Это изменяет итерацию на месте

Давайте возьмем простой пример построения очереди приоритетов из обычного списка целых чисел.

import heapq

a = [1, 4, 3, 5, 2]

print("List =", a)

# Convert the iterable (list) into a min-heap in-place
heapq.heapify(a)

print("Min Heap =", a)

Выход

List = [1, 4, 3, 5, 2]
Min Heap = [1, 2, 3, 5, 4]

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

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

Для представления минимальной кучи из списка для узла с индексом i его дочерние элементы имеют индексы 2*i и 2*i+1 .

Для минимальной кучи родитель должен быть меньше, чем оба его ребенка!

Как вы можете видеть, второй список действительно следует за нашим свойством min-heap! Таким образом, мы убедились, что метод heapify() дает нам правильную минимальную кучу.

Теперь мы будем нажимать и выскакивать в/из нашей кучи.

import heapq

a = [1, 4, 3, 5, 2]

print("List =", a)

# Convert the iterable (list) into a min-heap in-place
heapq.heapify(a)

print("Min Heap =", a)

# Use heappush
heapq.heappush(a, 10)

print("After heappush(), Min Heap =", a)

# Use array indexing to get the smallest element
print(f"Smallest element in the heap queue = {a[0]}")

# Use heappop() and return the popped element
popped_element = heapq.heappop(a)

print(f"Popped element = {popped_element}, Min Heap = {a}")

Выход

List = [1, 4, 3, 5, 2]
Min Heap = [1, 2, 3, 5, 4]
After heappush(), Min Heap = [1, 2, 3, 5, 4, 10]
Smallest element in the heap queue = 1
Popped element = 1, Min Heap = [2, 4, 3, 5, 10]

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

import heapq

def heapsort(iterable):
    h = []
    for value in iterable:
        # Push the elements onto the heap
        heapq.heappush(h, value)
    # Keep popping the smallest elements and appending them to our sorted list
    return [heapq.heappop(h) for i in range(len(h))]

sorted_list = heapsort([1, 3, 5, 7, 9, 2, 4, 6, 8, 0])
print(sorted_list)

Выход

[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

Отлично! Действительно, мы использовали свойство очереди кучи для сортировки нашего списка!

Вывод

В этой статье мы узнали об использовании модуля Python heapq и увидели, как мы можем использовать свойство min-heap для сортировки нашего неупорядоченного списка.

Рекомендации

• Документация на Python по модулю heapq