Re: [Caml-list] Sorted list

[Brian Hurt <bhurt@spnz.org>]

I forgot a bit of analysis as to why I recommend that data structure, and 
not others.  The advantage a priority queue has is that peeking at the 
head node (highest priority) element is O(1), and in this case very fast. 
This is in comparison with the O(log N) cost of using a map or tree-based 
list.  I was assuming that since you were implementing a timer queue, the 
bulk of the accesses will be "has the next timer timed out yet?  No- 
moving on..."

You can implement a mutable version of the leftist heap, and keep a parent 
pointer in the node.  This allows you to remove an arbitrary node in O(log 
N) time, during the delete function (as opposed to waiting for the timer 
to time out to remove it).  But it's a lot more complicated- the idea is 
easier to see in the purely functional code.

If you want to use a map, have each element be a list of timers set to 
expire at the same time.

Brian