[Python-Dev] binary trees.

[Josiah Carlson]

"Vladimir 'Yu' Stepanov" <vys at renet.ru> wrote:
> 
> Martin v. Löwis wrote:
> > Vladimir 'Yu' Stepanov wrote:
> >   
> >> Yes. I understood it when resulted a set example.
> >>     
> >>> However, as I just said, people usually don't remove items from
> >>> just-sorted lists, they tend to iterate over them via 'for i in list:' .
> >>>   
> >>>       
> >> Such problem arises at creation of the list of timers.
> >>     
> >
> > For a list of timers/timeout events, a priority queue is often the best
> > data structure, which is already available through the heapq module.
> >   
> 
> It is in most cases valid so. heapq very much approaches for these purposes.
> The unique problem is connected with removal of an any element from the 
> list.

For this particular problem, usually you don't want to say, "remove time
4.34252 from the heap", you want to say "remove the (time,event) pair
given the event X, from the heap", where you have in your heap (time,
event) pairs.

For hashable events, you can create a class which implements enough
list-like semantics to allow it to work like a heap for event timing
(__getitem__, __setitem__, __len__, .pop(-1) is about it, if I remember
correctly), but also allows you to remove arbitrary events (as items are
shifted around in the heap, you update pointers from a dictionary).

The details are a bit annoying to get right, but it is possible.


 - Josiah