ejp@bohra.cpg.oz (Esmond Pitt) (11/10/89)
A while ago on (I believe) this newsgroup, there was a discussion of a revised heapsort algorithm, published in 1987 or 1988, using a binary search over the path to the leaf node. Unfortunately I have wiped my copies of the discussion. Could some kind soul please either (a) mail me the gist, or better still the article(s), (b) provide me with further information, or at least (c) cite the reference. Thank you very much. -- Esmond Pitt, Computer Power Group ejp@bohra.cpg.oz
rawlins@iuvax.cs.indiana.edu (Gregory J. E. Rawlins) (11/10/89)
In article <110@bohra.cpg.oz> ejp@bohra.cpg.oz (Esmond Pitt) writes:
-A while ago on (I believe) this newsgroup, there was a discussion of a
-revised heapsort algorithm, published in 1987 or 1988, using a binary
-search over the path to the leaf node.
I don't recall that it was discussed in this newsgroup but the binary search
on heap paths result was first presented at ICALP 82. It has appeared as
G. Gonnet and J. I. Munro, ``Heaps on Heaps,'' SIAM J. Comp. 15(4), 964-971.
gregory.