Очередь приоритетов в Python

Очереди приоритетов — это фундаментальная структура данных в информатике, используемая для управления элементами со связанными приоритетами.

В отличие от традиционных очередей, где элементы обрабатываются в порядке «первым пришел — первым обслужен»(FIFO), приоритетные очереди обрабатывают элементы в зависимости от их приоритета, при этом элементы с более высоким приоритетом обрабатываются раньше элементов с более низким приоритетом.

В Python очереди с приоритетами обычно реализуются с использованием модуля heapq или внешних библиотек, таких как Queue.PriorityQueue.

Содержание

Какова очередь приоритетов?

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

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

Как работают?

Очереди приоритетов в Python можно реализовать с использованием базовых структур данных, таких как кучи или сбалансированные деревья. Наиболее распространенной реализацией является использование структуры данных кучи из-за ее эффективности в поддержании элемента с самым высоким(или самым низким) приоритетом наверху.

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

С модулем heapq

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

Он включает в себя такие функции, как heappush() для добавления элементов и heappop() для удаления наименьшего элемента.

Пример:

import heapq

pq = []

def add_task(task, priority):
    heapq.heappush(pq,(priority, task))

def get_highest_priority_task():
    if pq:
        return heapq.heappop(pq)[1]
    else:
        return None

add_task('Task 1', 3)
add_task('Task 2', 1)
add_task('Task 3', 2)
print(get_highest_priority_task())
print(get_highest_priority_task())
print(get_highest_priority_task())

Функция add_task( task, Priority) предназначена для добавления задачи в очередь приоритетов в Python с указанным приоритетом. Мы используем heapq.heappush() для поддержания свойства кучи, чтобы гарантировать, что задача с более низкими значениями приоритета находится ближе к началу очереди.

def add_task(task, priority):
    heapq.heappush(pq,(priority, task))

Функция get_highest_priority_task() возвращает и удаляет задачу с наивысшим приоритетом из очереди приоритетов Python.

При этом используется heapq.heappop() для эффективного извлечения задачи с наименьшим значением приоритета. Если очередь пуста, возвращается None.

def get_highest_priority_task():
    if pq:
        return heapq.heappop(pq)[1]
    else:
        return None

Выход:

Task 2
Task 3
Task 1

Результат можно увидеть на скриншоте ниже после выполнения кода в PyCharm.

Выполнение кода в PyCharm

Класс queues.PriorityQueue

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

Вот пример, демонстрирующий использование queues.PriorityQueue в Python:

from queue import PriorityQueue

pq = PriorityQueue()

def add_task(task, priority):
    pq.put((priority, task))

def get_highest_priority_task():
    if not pq.empty():
        return pq.get()[1]
    else:
        return None

add_task('California Data Processing', 3)
add_task('New York Data Analysis', 1)
add_task('Texas Data Entry', 2)
print(get_highest_priority_task())
print(get_highest_priority_task())
print(get_highest_priority_task())

Я создал функцию с именем «add_task», которая добавляет задачу в приоритетную очередь с указанным приоритетом. Требуется два параметра.

Функции добавляют задачу в очередь приоритетов в Python с помощью метода put() класса PriorityQueue, при этом приоритет указывается в виде кортежа вместе с задачей.

def add_task(task, priority):
    pq.put((priority, task))

Я также создал в Python еще одну функцию под названием «get_highest_priority_task()», которая выдает и удаляет задачу с наивысшим приоритетом из очереди приоритетов. Это проверяет, не пуста ли очередь приоритетов, с помощью метода empty() класса PriorityQueue.

Если очередь не пуста, она извлекает верхний элемент с помощью метода get(), который возвращает кортеж (приоритет, задача). Функция возвращает только задачу (индекс кортежа 1) без приоритета в Python.

def get_highest_priority_task():
    if not pq.empty():
        return pq.get()[1]
    else:
        return None

Выход:

New York Data Analysis
Texas Data Entry
California Data Processing

На снимке экрана ниже показан код, реализованный в редакторе PyCharm.

приоритетная очередь в Python

Как использовать в виде списка

Чтобы реализовать очередь приоритетов в Python в списке, нам нужно объявить пустой список Python, в который элементы вставляются с помощью метода Append() класса списка. Затем список сортируется по возрастанию. Цикл While извлекает элементы с помощью метода pop().

Пример:

employee = []
employee.append((5, 'Nick'))
employee.append((1, 'Rohan'))
employee.append((3, 'Jack'))
employee.sort(reverse=True)
while employee:
    employee_tuple = employee.pop()
    print(employee_tuple)

После написания приведенного выше кода (реализация очереди приоритетов Python) элемент сортирует и удаляет элементы из очереди на основе их очереди приоритетов Python.

Выход:

(1, 'Rohan')
(3, 'Jack')
(5, 'Nick')

На скриншоте ниже вы можете посмотреть реализацию очереди приоритетов Python.

Реализация очереди приоритетов

Очередь с максимальным приоритетом

В очереди максимального приоритета Python список будет упорядочен по убыванию их приоритета. Цикл While извлекает элементы с помощью метода pop(0).

Пример:

employee = []
employee.append((5, 'Nick'))
employee.append((1, 'Ross'))
employee.append((3, 'Jack'))
employee.sort(reverse=True)
while employee:
    employee_tuple = employee.pop()
    print(employee_tuple)

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

Выход:

(1, 'Ross')
(3, 'Jack')
(5, 'Nick')

На скриншоте ниже вы можете увидеть очередь с максимальным приоритетом в Python.

Очередь с максимальным приоритетом Python

Заключение

Очереди приоритетов Python — это важная структура данных для управления элементами со связанными приоритетами.

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

Добавить комментарий