> Check out http://en.wikipedia.org/wiki/Binary_heap in particular the section
> on Heap implementation which is directly applicable to the Heap class in
> Squeak. Note that the heap property does not require the heap to be totally
> sorted; the following two Heaps are both valid:

Well, so much for the computing science degree (boy it's been a while
since my last algorithms class :)... I was basing my assumption on the
fact that the class comment for the Heap directly compares it to the
SortedCollection class (in terms of complexity), which, to me, implies
they are functionally equivalent.  After all, it's hardly fair
comparing a fully sorted collection to an implementation that doesn't
fully sort. :)

Thanks!

Brett.