[EMAIL PROTECTED] wrote:
> Here is my version:
> [...]
>
> On 21 Sep , Chris Dornan wrote:
> > When would a heap sort be preferable to a merge sort?
>
> a) When you want to explain the imperative heapsort
But the heapsort you give is nothing like the standard imperative
heapsort! Yes, it uses a heap, but not the binary heap used by
standard heapsort. Instead, it uses the functional equivalent
of multi-pass pairing heaps[1]. Larry Paulson's "ML for the
Working Programmer" includes a functional heapsort that is
much closer in spirit to the standard imperative version, and
so is probably superior for pedagogical purposes. (Although I expect
that your version will be much faster in practice.)
Chris
[1] Fredman, Sedgewick, Sleator, and Tarjan.
"The pairing heap: A new form of self-adjusting heap"
Algorithmica 1(1):111-129, 1986.
