On 4 Oct , Chris Okasaki wrote:
> But the heapsort you give is nothing like the standard imperative
> heapsort!
Point taken, although I think 'nothing like' is overstating the case.
> Yes, it uses a heap, but not the binary heap used by standard
> heapsort.
Perfectly true. I only said that you could use my version when
explaining it, not that it would be suitable for the whole
explanation. What I had in mind was that this sort is easier to
explain, and gets some of the concepts across. Most of the
complication in imperative heapsort is to do with keeping the heaps in
place in a fixed size array.
> Larry Paulson's "ML for the Working Programmer" includes a
> functional heapsort ... is probably superior for pedagogical
> purposes.
Well, I'd certainly want to go on to describe this in our hypothetical
pedagogical situation :-) Mind you, I haven't done any teaching since
I got ill (which was before I wrote the sort), so I have no
experimental evidence. The approach above might just prove confusing.
Perhaps I should just have said that a use for it is as an answer to
people who say it's difficult (or impossible) to write a heapsort
functionally, which was what prompted me to write it in the first
place.
> [1] Fredman, Sedgewick, Sleator, and Tarjan.
> "The pairing heap: A new form of self-adjusting heap"
> Algorithmica 1(1):111-129, 1986.
Many thanks for this reference, of which I was unaware.
Jon
--
Jon Fairbairn [EMAIL PROTECTED]
18 Kimberley Road [EMAIL PROTECTED]
Cambridge CB4 1HH +44 1223 570179 (pm only, please)
