Перерыв в очереди приоритетов с использованием python

Question

Я использую очередь кучи для реализации алгоритма, когда я добавляю новые узлы в свою очередь, они сортируются с помощью эвристической функции: например, heappush (queue, (score (node)), который является фантастическим, кроме того, что, когда я пришел, чтобы вытащить следующий узел из очереди, я хочу, чтобы последний добавленный узел, в отличие от первого добавленного узла, возвращался к тому, что возвращается. как я могу получить последние узлы, добавленные в очередь, не нарушая их?

Я думаю, что я мог бы просто начать итерацию в первом элементе, и в то время как следующий элемент имеет тот же балл, продолжайте. Затем, когда я нахожу последний элемент с этим счетом, я выбираю его и удаляю из списка. Это, очевидно, не очень эффективно, и разбивает временную сложность очереди приоритетов?

Я застрял на этом, и я не могу понять, как это сделать.

Спасибо.

изменить; Используя счетчик, как это было предложено не будет работать (возможно, я неправильно понял)

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

Теперь очередь заказан неправильно, и «б», которая является хуже, чем вариант «а» стоит перед ним.

EDIT 2:

Какого черта?

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

Answer 1

Один очень простой способ - добавить средний термин, содержащий метку времени или значение счетчика. Так, например:

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

Как отмечает AGF, это подход, используемый в heapq документы, используя только отрицательные индексы. (Реализация там также включает в себя прекрасную процедуру удаления задачи и смены приоритета).