Как устроена и как хранится самописная очередь с приоритетом

Что проверяют

Понимаете ли вы, как двоичная куча укладывается в обычный список и откуда берётся O(log n). Следом часто просят написать push и pop или спрашивают, что будет с элементами одинакового приоритета.

Как отвечать

Сравните варианты хранения:

• несортированный список: вставка O(1), извлечение O(n) линейным поиском;
• сортированный список: извлечение O(1), вставка O(n) из-за сдвига (bisect.insort находит место за O(log n), но сдвиг остаётся);
• двоичная куча: вставка и извлечение O(log n), вершина O(1), построение из готового списка O(n). Её и выбирают.

Куча лежит в плоском списке без указателей: у элемента i дети на 2*i+1 и 2*i+2, родитель на (i-1)//2. Инвариант min-кучи: родитель не больше детей. push добавляет элемент в конец и поднимает его, пока он меньше родителя. pop меняет корень с последним элементом, отрезает хвост и опускает новый корень, меняя его с меньшим из детей.

В стандартной библиотеке ровно это делает heapq, куча там минимальная, для максимальной приоритет берут со знаком минус. queue.PriorityQueue это потокобезопасная обёртка над heapq, для корутин есть asyncio.PriorityQueue.

Элемент храните как (priority, seq, item), где seq берётся из itertools.count(): равные приоритеты выходят в порядке поступления, а сами item не сравниваются. Смену приоритета делают ленивым удалением: старую запись помечают, новую добавляют, помеченные пропускают при pop.

Если очередь должна переживать рестарт, нужен внешний носитель: sorted set в Redis (ZADD, ZPOPMIN) или таблица с индексом по приоритету и выборкой FOR UPDATE SKIP LOCKED.

Где спотыкаются

Кладут в кучу (priority, item). При равных приоритетах Python сравнит сами объекты, и для словарей или своих классов получится TypeError.

Путают кучу с отсортированным массивом. Она упорядочена только от родителя к детям, поэтому обход списка подряд не даёт элементы по приоритету.

Путают сложности: сортируют весь список ради одного извлечения, это O(n log n) там, где хватило бы O(n), или считают, что сортированный связный список быстро вставляет. Вставка там O(n) из-за поиска места.