How to remove item from heap efficiently?
Sven R. Kunze
srkunze at mail.de
Tue Jan 12 11:18:50 EST 2016
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
More information about the Python-list
mailing list