How to remove item from heap efficiently?

[Cem Karan]

On Jan 12, 2016, at 11:18 AM, "Sven R. Kunze" <srkunze at mail.de> wrote:

> 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.

Is that so?  I'll be honest, I never tested its asymptotic performance, I just assumed that he had a dict coupled with a heap somehow, but I never looked into the code.

That said, IMHO using a dict interface is the way to go for priority queues; it really simplified my code using it!  This is my not-so-subtle way of asking you to adopt the MutableMapping interface for your wrapper ;)

Thanks,
Cem Karan