Статья Автор: Деникина Н.В., Деникин А.В.

Куча с приоритетом

Куча с приоритетом (priority queue) — это структура данных, которая позволяет эффективно находить и удалять элемент с наивысшим (или наименьшим) приоритетом.

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

Основные операции

Добавление элемента: heapq.heappush(heap, item)

Добавляет элемент в кучу, сохраняя свойства кучи.

Извлечение элемента с наименьшим приоритетом: heapq.heappop(heap)

Удаляет и возвращает элемент с наименьшим значением из кучи.

Преобразование списка в кучу: heapq.heapify(list)

Преобразует обычный список в кучу за время O(n).

Получение минимального элемента без удаления: heap[0]

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

Пример

import heapq

# Создание пустой кучи
heap = []

# Добавление элементов в кучу
heapq.heappush(heap, 10)
heapq.heappush(heap, 5)
heapq.heappush(heap, 20)

# Извлечение минимального элемента
print(heapq.heappop(heap))  # Вывод: 5

# Преобразование списка в кучу
lst = [7, 1, 3, 5, 2]
heapq.heapify(lst)
print(lst)  # Вывод: [1, 2, 3, 5, 7]

# Получение минимального элемента без удаления
print(lst[0])  # Вывод: 1

Особенности

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

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

heapq.heappush(heap, -10)
heapq.heappush(heap, -5)
print(-heapq.heappop(heap))  # Вывод: 10

Применение

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

Алгоритм Дейкстры для поиска кратчайшего пути.
Сортировка (например, heapsort).
Управление задачами с разными приоритетами.

Сложность операций

Добавление элемента: O(log n)
Извлечение элемента: O(log n)
Преобразование списка в кучу: O(n)
Получение минимального элемента: O(1)

Чтобы оставить комментарий нужна авторизация

Печать