 <p>One very simple way is to add a middle term containing a timestamp or a counter value. So for example: </p> <pre><code>&gt;&gt;&gt; heap = [] &gt;&gt;&gt; counter = itertools.count() &gt;&gt;&gt; for i in range(10): ... heapq.heappush(heap, (i, -next(counter), str(i) + ' oldest')) ... heapq.heappush(heap, (i, -next(counter), str(i) + ' newest')) ... &gt;&gt;&gt; heapq.heappop(heap) (0, -1, '0 newest') &gt;&gt;&gt; heapq.heappop(heap) (0, 0, '0 oldest') &gt;&gt;&gt; heapq.heappop(heap) (1, -3, '1 newest') &gt;&gt;&gt; heapq.heappop(heap) (1, -2, '1 oldest') </code></pre> <p>As agf mentions, this is the approach used by the <a href="http://docs.python.org/library/heapq.html#priority-queue-implementation-notes" rel="nofollow"><code>heapq</code></a> docs, only using negative indices. (The implementation there also includes a nice task-removal and priority-change routine.)</p>