На этом шаге мы вспомним про очередь с приоритетом.

Очереди с приоритетом были описаны на 31 шаге. Нам понадобится очередь с приоритетом для алгоритма Ярника. Для полноты картины мы воссоздадим здесь класс PriorityQueue из 31 шага со специальными инструкциями import, которые предполагают, что этот класс будет помещен в отдельный файл (файл priority_queue.py).

from typing import TypeVar, Generic, List
from heapq import heappush, heappop

T = TypeVar('T')


class PriorityQueue(Generic[T]):
    def __init__(self) -> None:
        self._container: List[T] = []

    @property
    def empty(self) -> bool:
        return not self._container  # не Тrue для пустого контейнера

    def push(self, item: T) -> None:
        heappush(self._container, item)  # поместить в очередь по приоритету

    def pop(self) -> T:
        return heappop(self._container)  # извлечь по приоритету

    def __repr__(self) -> str:
        return repr(self._container)

Архив с файлом можно взять здесь.

На следующем шаге мы рассмотрим вычисление общего веса взвешенного пути.

Предыдущий шаг Содержание Следующий шаг