On Tue, Oct 23, 2007 at 10:54:35AM -0400, der Mouse wrote:
> >> 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.

Sure, but if you do that it is not that much cheaper then an red black
tree anymore.

Joerg