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

Groups > comp.lang.python > #101512

Re: How to remove item from heap efficiently?

Show key headers only | View raw

On Jan 11, 2016, at 9:53 AM, srinivas devaki <mr.eightnoteight@gmail.com> wrote:

> 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.

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,
Cem Karan

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

Thread

Re: How to remove item from heap efficiently? Cem Karan <cfkaran2@gmail.com> - 2016-01-11 21:48 -0500

csiph-web