How to remove item from heap efficiently?

[Sven R. Kunze]

On 12.01.2016 03:48, Cem Karan wrote:
>
> Jumping in late, but...
>
> If you want something that 'just works', you can use HeapDict:
>
> http://stutzbachenterprises.com/
>
> I've used it in the past, and it works quite well.  I haven't tested its asymptotic performance though, so you might want to check into that.

Thanks for replying here. I've come across these types of 
wrappers/re-implementations of heapq as well when researching this issue. :)

Unfortunately, they don't solve the underlying issue at hand which is: 
"remove item from heap with unknown index" and be efficient at it (by 
not using _heapq C implementation).


So, I thought I did another wrapper. ;) It at least uses _heapq (if 
available otherwise heapq) and lets you remove items without violating 
the invariant in O(log n). I am going to make that open-source on pypi 
and see what people think of it.

Best,
Sven