>> A 'heap' [...]
> I'm so sure about the heap.  We can't just use the classic binary
> heap as that needs a resizable array we don't have.

A heap is a particular subclass of binary tree.  Storing it in an array
is just a way to optimize away the parent and child pointers, and make
it easy to find the insertion point for new nodes.

If you explicitly store the parent and child pointers, the only thing
left is finding the insertion point, and that is fairly easy to do by
keeping a separate count of the heap's size and using its bits to
direct a walk down from the root.

Of course insert and delete are still log(N) operations; all a heap
buys you is that it's very easy to find the first element in whatever
the heap's sort order is.

For that matter, why couldn't we have a resizable array?  That's what I
used when I implemented timer sockets.  (There's probably a reason
which will be blindingly obvious to me once someone points it out....)

/~\ The ASCII				der Mouse
\ / Ribbon Campaign
 X  Against HTML	       mouse@rodents.montreal.qc.ca
/ \ Email!	     7D C8 61 52 5D E7 2D 39  4E F1 31 3E E8 B3 27 4B