Tie Breaking in einer Prioritätswarteschlange mit Python

Question

Ich benutze eine Heap-Warteschlange, um einen Algorithmus zu implementieren, wenn ich neue Knoten zu meiner Warteschlange hinzufügen, sind sie nach einer heuristischen Funktion sortiert: zB heappush (Warteschlange, (Score (Knoten), node)), was fantastisch ist, abgesehen davon, dass ich, wenn ich den nächsten Knoten aus der Warteschlange platziere, den zuletzt hinzugefügten Knoten haben möchte, im Gegensatz zum ersten hinzugefügten Knoten, was heappop zurückgibt. Wie kann ich die neuesten Knoten zur Warteschlange hinzufügen, ohne sie zu unterbrechen?

Ich denke, ich könnte gerade Iteration am ersten Element beginnen, und während das nächste Element die gleiche Punktzahl hat, weiter. Wenn ich dann das letzte Element mit dieser Punktzahl finde, wähle ich es aus und entferne es aus der Liste. Dies ist natürlich nicht sehr effizient und durchbricht die Zeitkomplexität einer Prioritätswarteschlange.

Ich bin auf diesem fest und ich kann nicht einen Weg, es zu tun.

Danke.

bearbeiten; Mit Hilfe eines Zählers, wie vorgeschlagen wird nicht funktionieren (vielleicht habe ich das falsch verstanden)

>>> queue = [] 
>>> heappush(queue, (2, 0, 'a')) 
>>> heappush(queue, (3, -1, 'b')) 
>>> queue 
[(2, 0, 'a'), (3, -1, 'b')] 
>>> heappush(queue, (2, -2, 'c')) 
>>> queue 
[(2, -2, 'c'), (3, -1, 'b'), (2, 0, 'a')] 

Nun ist die Warteschlange falsch bestellt wird, und ‚b‘, das ist eine schlechtere Wahl als ‚a‘, bevor er platziert wird.

EDIT 2:

Was zur Hölle?

>>> heappop(queue) 
(2, -2, 'c') 
>>> queue 
[(2, 0, 'a'), (3, -1, 'b')] 
>>> 

Answer 1

Ein sehr einfacher Weg ist es, einen mittleren Term hinzuzufügen, der einen Zeitstempel oder einen Zählerwert enthält. So zum Beispiel:

>>> heap = [] 
>>> counter = itertools.count() 
>>> for i in range(10): 
...  heapq.heappush(heap, (i, -next(counter), str(i) + ' oldest')) 
...  heapq.heappush(heap, (i, -next(counter), str(i) + ' newest')) 
... 
>>> heapq.heappop(heap) 
(0, -1, '0 newest') 
>>> heapq.heappop(heap) 
(0, 0, '0 oldest') 
>>> heapq.heappop(heap) 
(1, -3, '1 newest') 
>>> heapq.heappop(heap) 
(1, -2, '1 oldest') 

Wie agf erwähnt, ist dies der Ansatz des heapq docs verwendet, nur negativen Indizes verwenden. (Die Implementierung enthält auch eine nette Routine zum Entfernen und Ändern von Aufgaben.)