On Jan 11, 2016, at 9:53 AM, srinivas devaki <mr.eightnotei...@gmail.com> wrote:
> On Jan 11, 2016 12:18 AM, "Sven R. Kunze" <srku...@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 -- https://mail.python.org/mailman/listinfo/python-list
