Interrumpir el tie en una cola de prioridad usando python

Question

Estoy usando una cola de heap para implementar un algoritmo, cuando agrego nuevos nodos a mi cola, están ordenados por una función heurística: por ejemplo, heappush (queue, (puntaje (nodo)), que es fantástico, aparte del hecho de que cuando vengo a sacar el siguiente nodo de la cola, quiero el nodo agregado más recientemente, a diferencia del primer nodo agregado, que es lo que devuelve heappop. ¿Cómo puedo obtener los nodos más recientes agregados a la cola sin romperlos?

Supongo que podría comenzar la iteración en el primer elemento, y mientras el siguiente elemento tiene el mismo puntaje, continúe. Luego, cuando encuentro el elemento final con ese puntaje, lo selecciono y lo quito de la lista. Obviamente, esto no es muy eficiente y rompe la complejidad del tiempo de una cola de prioridad.

Estoy atascado en esto y no puedo encontrar una manera de hacerlo.

Gracias.

editar; El uso de un contador, como se sugiere no va a funcionar (tal vez he entendido bien)

>>> 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')] 

Ahora la cola se ordena de forma incorrecta, y 'b', que es una opción peor que 'a' se coloca antes de ella.

EDIT 2:

¿Qué demonios?

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

Answer 1

Una manera muy simple es agregar un término medio que contiene una marca de tiempo o un valor de contador. Así, por ejemplo:

>>> 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') 

Como se menciona AGF, este es el enfoque utilizado por los heapq documentos, sólo con índices negativos. (La implementación también incluye una buena rutina de eliminación de tareas y cambio de prioridad.)