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

Очередь с приоритетами^[1] широко используется для кучи и представляет собой несколько проблем с реализацией:

• Стабильность сортировки: как получить две задачи с одинаковыми приоритетами в том порядке, в котором они были добавлены изначально?
• Прерывания сравнения кортежей для пар (приоритет, задача), если приоритеты равны и задачи не имеют порядка сравнения по умолчанию.
• Если приоритет задачи меняется, как переместить ее на новую позицию в куче?
• Или, если нужно удалить отложенную задачу, как ее найти и удалить из очереди?

Решение первых двух проблем заключается в сохранении записей в виде трехэлементного списка, включающего приоритет, количество записей и задачу. Счетчик записей служит для разрешения конфликтов, поэтому две задачи с одинаковым приоритетом возвращаются в порядке их добавления. И поскольку нет двух одинаковых счетчиков записей, сравнение кортежей никогда не будет пытаться напрямую сравнить две задачи.

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

from dataclasses import dataclass, field
from typing import Any

@dataclass(order=True)
class PrioritizedItem:
    priority: int
    item: Any=field(compare=False)

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

Удаление записи или изменение ее приоритета труднее, потому что это нарушит инварианты структуры кучи. Таким образом, возможное решение - пометить запись как удаленную и добавить новую запись с измененным приоритетом:

# список записей, 
# расположенных в куче
pq = []
# отображение задач на записи
entry_finder = {}
# заполнитель для 
# удаленного задания
REMOVED = '<removed-task>'
# Количество уникальных 
# последовательностей
counter = itertools.count()

def add_task(task, priority=0):
    """Добавить новую задачу или 
        обновить приоритет существующей задачи
    """
    if task in entry_finder:
        remove_task(task)
    count = next(counter)
    entry = [priority, count, task]
    entry_finder[task] = entry
    heappush(pq, entry)

def remove_task(task):
    """Отметить существующее задание как УДАЛЕНО. 
        Если не найден, то KeyError.
    """
    entry = entry_finder.pop(task)
    entry[-1] = REMOVED

def pop_task():
    """Удалить и вернуть задачу с самым низким приоритетом.
        Если не найден, то KeyError.
    """
    while pq:
        priority, count, task = heappop(pq)
        if task is not REMOVED:
            del entry_finder[task]
            return task
    raise KeyError('pop from an empty priority queue')

[1]. Очередь с приоритетами - абстрактный тип данных, поддерживающий две обязательные операции - добавить элемент и извлечь максимум (минимум). Предполагается, что для каждого элемента можно вычислить его приоритет - действительное число или в общем случае элемент линейно упорядоченного множества.