Python和內置堆

Question

目前，我想寫使用內置的heapq庫Python中的優先級隊列。然而，我試圖弄清楚Python在打破平局方面所做的工作，我想要有一個特定的條件，在那裏我可以決定打破平局會發生什麼，而不是heapq庫，似乎幾乎可以選擇某些東西隨機排隊。是否有人知道重寫破解條件的方法，還是從頭開始構建優先隊列更容易？

Answer 1

heapq使用隊列項目（__le__和朋友）的內在比較。要解決此限制的一般方法是被稱爲「裝飾/去除裝飾」好老辦法 - 這就是我們使用排序做，引入了key=參數之前就有。

簡而言之，您入隊和出隊，不僅僅是您關心的項目（「有效載荷」），而是將項目「裝飾」爲需要考慮的「鑰匙」開頭的元組。因此，例如，如果您想通過x屬性優先化排列元組，那麼這將是正常的，因爲按照插入隊列的時間將關係中斷 - 當然，當您將隊列解除排隊時，通過取[-1]通過排隊獲得的元組的第一項。

所以，只需將「次要鑰匙」放入您要排隊的「裝飾」元組中的「tie-breaking」中即可。