[Python-Dev] collections.sortedtree

[Antoine Pitrou]

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.