On Jan 12, 2016, at 11:18 AM, "Sven R. Kunze" <srku...@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 -- https://mail.python.org/mailman/listinfo/python-list
