bearophile wrote:
For Andrei: in my last post I have suggested to remove from the heap the references to the sub-ranges as soon they are exhausted. But lot of tests of mine have shown me that's often not the most efficient strategy: http://www.fantascienza.net/leonardo/ar/list_deletions.html So better things are possible. The most refined strategy may be overkill, but some medium strategy may be OK.
I don't think that applies here. Unstable removal is O(1) and restoring the heap property is O(log n) in theory and very close to O(1) in practice.
Andrei
