[Python-Dev] collections.sortedtree (original) (raw)

Antoine Pitrou solipsis at pitrou.net
Wed Mar 26 23🔞36 CET 2014

On Wed, 26 Mar 2014 18:14:19 -0400 Ben Darnell <ben at bendarnell.com> wrote:

> > > > If the canceled timer lingers in the heapq till its expiry (in 10 > > minutes), the size is 100 * 10 * 60 = 60,000. The CPU has to wake up > > constantly to clear the expired timers. > > Ideally, I think you should be able to replace the cancelled item with > the last item in the heap and then fix the heap in logarithmic time, > but the heapq API doesn't seem to provide a way to do this.

Heaps provide easy access to the first item, but you can't find the last element without scanning the whole thing.

I was talking about the last element, not the largest. The point of replacing with the last element is that shrinking is O(1).

Regards

Antoine.

More information about the Python-Dev mailing list