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

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

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

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

Спасибо.

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

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

Теперь очередь упорядочена неправильно, и перед ней ставится 'b', который является худшим вариантом, чем 'a'.

РЕДАКТИРОВАТЬ 2:

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

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