How to remove item from heap efficiently?
Cem Karan
cfkaran2 at gmail.com
Mon Jan 11 21:48:34 EST 2016
On Jan 11, 2016, at 9:53 AM, srinivas devaki <mr.eightnoteight at gmail.com> wrote:
> On Jan 11, 2016 12:18 AM, "Sven R. Kunze" <srkunze at 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
More information about the Python-list
mailing list