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

Groups > comp.lang.python > #101549 > unrolled thread

Re: How to remove item from heap efficiently?

Back to article view | Back to comp.lang.python

This discussion starts older than the indexed window; earlier articles aren't shown. The article labeled Started by below is the oldest one visible, not the original post.

Contents

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

#101549 — Re: How to remove item from heap efficiently?

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

[toc] | [standalone]

Back to top | Article view | comp.lang.python

csiph-web