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

Groups > comp.lang.python > #101483 > 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? srinivas devaki <mr.eightnoteight@gmail.com> - 2016-01-11 20:23 +0530

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

On Jan 11, 2016 12:18 AM, "Sven R. Kunze" <srkunze@mail.de> wrote:
> Indeed. I already do the sweep method as you suggested. ;)
>
> Additionally, you provided me with a reasonable condition when to do the
sweep in order to achieve O(log n). Thanks much for that. I currently used
a time-bases approached (sweep each 20 iterations).
>
> PS: Could you add a note on how you got to the condition (
2*self.useless_b > len(self.heap_b))?
>

oh that's actually simple,
that condition checks if more than half of heap is useless items.
the sweep complexity is O(len(heap)), so to keep the extra amortized
complexity as O(1), we have to split that work(virtually) with O(len(heap))
operations, so when our condition becomes true we have done len(heap)
operations, so doing a sweep at that time means we splitted that
work(O(len(heap))) with every operation.

[toc] | [standalone]

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

csiph-web