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). > 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. -- http://mail.python.org/mailman/listinfo/python-list
