Python и встроенная куча

Question

В данный момент я пытаюсь написать приоритетную очередь в Python, используя встроенную библиотеку heapq. Тем не менее, я застрял, пытаясь понять, что Python делает с разрывом связей, я хочу иметь конкретное условие, где я могу диктовать, что происходит с разрывом связей, вместо библиотеки heapq, которая, кажется, почти что-то выбивает очередь наугад. Кто-нибудь знает способ переписать условие разрыва связи или будет проще построить очередь с нуля с нуля?

Answer 1

heapq использует внутренние сравнения элементов очереди (__le__ и друзей). Общий способ обойти это ограничение - это старый добрый подход, известный как «decorate / undecorate» - это то, что мы делали при сортировке до того, как там был введен параметр key=.

Проще говоря, вы ставите в очередь и удаляете из очереди не только элементы, которые вас интересуют («полезная нагрузка»), но скорее элементы, «декорированные» в кортежи, которые начинаются с «ключей», которые необходимо учитывать heapq Так, например, было бы нормально поставить в очередь кортеж типа (foo.x, time.time(), foo), если вы хотите установить приоритеты с помощью атрибута x со связями, разорванными во время вставки в очередь - конечно, когда вы удаляете из очереди "undecorate", взяв [-1] элемент кортежа, который вы получите, выкинув очередь.

Итак, просто вставьте «второстепенные ключи», которые вы должны рассматривать как «разрывающие связи», в «украшенный» кортеж, который вы ставите в очередь, ПОСЛЕ тех, чьи «связи» вы хотите разорвать таким образом.