heapdict should do a stable sort

[andreasvc]

When items with the same priority are inserted, they are not popped in the order that they were inserted. The order seems to be the reverse (LIFO instead of FIFO). Python's heapq and sorted do maintain stable sort. In terms of priorities it makes sense that for all items with the same priority, the one that has been waiting the longest should go first.

I tried changing some things in the code to see if it could easily be fixed (the len(heap) part of the wrappers seemed related), but unfortunately there are no comments.

[DanielStutzbach]

Are you sure that heapq is stable? Heapsorts are not normally stable sorts.

[andreasvc]

I was going by heapq.nsmallest, which appears to be stable; indeed heapq.heapify is not stable. Is it difficult to make heapdict stable, then? Including the len(heap) in the comparisons might do the trick I thought. What are they used for anyway? And why don't you use heapq?

[DanielStutzbach]

As far as I know, there is no easy way to make a heapsort into a stable sort. You could always use (priority, current_time) as the priority.

heapq doesn't support an efficient decrease-key operation, which is needed in some algorithms (e.g. Dijkstra's).

[andreasvc]

I understand the point of heapdict, of course. I meant why self.heap in heapdict.py doesn't use heapq, which provides heap operations implemented efficiently in C. One reason I can imagine is that heapq doesn't have a "key" option, but if you order the wrapper like [value, len, key], that might not be a problem.