Python priority queuing

Question

I use heap queue to implement the algorithm, when I add new nodes in turn, they are sorted using a heuristic function: for example, heappush (queue, (score (node), node)), which is fantastic, in addition to the fact that, when I came to release the next node from the queue, I want the last added node, as opposed to the first added node, which is what heappop returns. how can i get the last nodes added to the queue without breaking it?

I assume that I could just start the iteration in the first element, and as long as the next element has the same score, continue. Then, when I find the last item with this account, I select it and remove it from the list. Is this obviously not very effective and breaks the time complexity of the priority queue?

I am stuck on this and I cannot figure out how to do this.

Thanks.

edit; Using a counter, as suggested, will not work (maybe I misunderstood)

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

Now the queue is not ordered correctly, and before it is placed 'b', which is worse than 'a'.

EDIT 2:

What the heck?

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

Answer 1

One very simple way is to add an average term containing a timestamp or counter value. For example:

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

As agf mentions, this is the approach used by heapq docs, only using negative indices. (The implementation there also includes an excellent procedure for deleting a task and changing the priority.)