How to remove item from heap efficiently?

[srinivas devaki]

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.