Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.python > #101634

Re: How to remove item from heap efficiently?

Show all headers | View raw

On 13.01.2016 12:20, Cem Karan wrote:
> On Jan 12, 2016, at 11:18 AM, "Sven R. Kunze" <srkunze@mail.de> wrote:
>
>> 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.

My concern about that specific package is a missing C-implementation. I 
feel that somewhat defeats the whole purpose of using a heap: performance.

Asymptotic performance is still O(log n).

> 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 ;)

Could you elaborate on this? What simplified you code so much?

I have been using heaps for priority queues as well but haven't missed 
the dict interface so far. Maybe, my use-case is different.

Best,
Sven

Back to comp.lang.python | Previous | Next | Find similar | Unroll thread

Thread

Re: How to remove item from heap efficiently? "Sven R. Kunze" <srkunze@mail.de> - 2016-01-13 20:08 +0100

csiph-web