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

Groups > comp.lang.python > #101483

Re: How to remove item from heap efficiently?

Show key headers only | View raw

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.

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

Thread

Re: How to remove item from heap efficiently? srinivas devaki <mr.eightnoteight@gmail.com> - 2016-01-11 20:23 +0530

csiph-web