On 10 July 2013 19:56, Ian Kelly <ian.g.ke...@gmail.com> wrote: > On Wed, Jul 10, 2013 at 11:47 AM, Joshua Landau <jos...@landau.ws> wrote: >>>> If you care about speed, you might want to check the heapq module. >>>> Removing the smallest item and inserting a new item in a heap both cost >>>> O(log(N)) time, while finding the minimum in a dictionary requires >>>> iterating over the whole dictionary, which cost O(N) time. >> >> Actually, because it's a list under the hood I'd imagine push and pop >> still take O(n) time :/. > > It shouldn't. You can implement push by appending the new item and > then getting it into the right place by performing O(log n) swaps. > Likewise for pop, you can update the heap with O(log n) swaps and then > removing the tail element. Appending or removing the tail element of > a list is amortized O(1).
Genius. Bas replied off-list that it won't matter too much anyway as they're over-allocated, but this makes tons of sense. >> PS: It's faster to use heapreplace(...) than >> heappop(...);heappush(...) but it only saves a few %. > > The problem with heapreplace here is that the value to be pushed > is dependent on the value returned by pop. That's fine because indexing is much faster than pop. The "few %" was a real statistic from working, timed code. -- http://mail.python.org/mailman/listinfo/python-list
