Как использовать heapq Python

[

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

Автор: Moshe Zadka

Кучи и приоритетные очереди — малоизвестные, но удивительно полезные структуры данных. Они предлагают простое в использовании и эффективное решение для множества задач, связанных с поиском лучшего элемента в наборе данных. Модуль heapq входит в стандартную библиотеку Python. Он реализует все низкоуровневые операции с кучами, а также некоторые высокоуровневые общие применения для куч.

В этом руководстве вы узнаете:

• Что такое кучи и приоритетные очереди и как они связаны друг с другом
• Какие задачи могут быть решены с помощью кучи
• Как использовать модуль Python heapq, чтобы решить эти задачи

Данное руководство предназначено для Python-разработчиков, которые уже знакомы с такими концепциями, как списки, словари, множества и генераторы, и ищут более сложные структуры данных.

Вы можете попробовать примеры из этого руководства, скачав исходный код по следующей ссылке:

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

Кучи являются конкретными структурами данных, в то время как приоритетные очереди являются абстрактными структурами данных. Абстрактная структура данных определяет интерфейс, а конкретная структура данных определяет реализацию.

Кучи часто используются для реализации приоритетных очередей. Они являются наиболее популярной конкретной структурой данных для реализации абстрактной структуры данных приоритетной очереди.

Конкретные структуры данных также определяют гарантии производительности. Гарантии производительности определяют связь между размером структуры и временем, затрачиваемым на операции. Понимание этих гарантий позволяет предсказывать время работы программы при изменении размера входных данных.

Структуры данных, кучи и приоритетные очереди

Абстрактная структура данных определяет операции и отношения между ними. Например, абстрактная структура данных приоритетной очереди поддерживает три операции:

1. is_empty — проверка, пуста ли очередь.
2. add_element — добавление элемента в очередь.
3. pop_element — извлечение элемента с наивысшим приоритетом.

Приоритетные очереди часто используются для оптимизации выполнения задач, при которых целью является выполнение задачи с наивысшим приоритетом. После выполнения задачи её приоритет снижается, и она возвращается в очередь.

Существуют две разные конвенции для определения приоритета элемента:

1. Элемент с наибольшим приоритетом имеет высокий