title: Tie breaking in a priority queue using python
body: <p>I'm using a heap queue to implement an algorithm, when i add new nodes to my queue, they're sorted by a heuristic function: eg heappush(queue, (score(node), node)), which is fantastic, apart from the fact that when I come to pop the next node out of the queue, i want the most recently added node, as opposed to the first added node, which is what heappop returns. how can I get the most recent nodes added to the queue without breaking it?</p>
  
  <p>I guess I could just begin iteration at the first element, and while the next element has the same score, continue. Then when I find the final element with that score, I select it and remove it from the list. This obviously isn't very efficient though and breaks the time complexity of a priority queue?</p>
  
  <p>I'm stuck on this and I can't figure out a way to do it. </p>
  
  <p>Thanks.</p>
  
  <p>edit; Using a counter, as suggested will not work (perhaps I've misunderstood)</p>
  
  <pre><code>&gt;&gt;&gt; queue = []
  &gt;&gt;&gt; heappush(queue, (2, 0, 'a'))
  &gt;&gt;&gt; heappush(queue, (3, -1, 'b'))
  &gt;&gt;&gt; queue
  [(2, 0, 'a'), (3, -1, 'b')]
  &gt;&gt;&gt; heappush(queue, (2, -2, 'c'))
  &gt;&gt;&gt; queue
  [(2, -2, 'c'), (3, -1, 'b'), (2, 0, 'a')]
  </code></pre>
  
  <p>Now the queue is ordered incorrectly, and 'b' which is a worse option than 'a' is placed before it.</p>
  
  <p>EDIT 2:</p>
  
  <p>What the hell?</p>
  
  <pre><code>&gt;&gt;&gt; heappop(queue)
  (2, -2, 'c')
  &gt;&gt;&gt; queue
  [(2, 0, 'a'), (3, -1, 'b')]
  &gt;&gt;&gt; 
  </code></pre>