Path: utzoo!attcan!utgpu!watmath!iuvax!rawlins
From: rawlins@iuvax.cs.indiana.edu (Gregory J. E. Rawlins)
Newsgroups: comp.theory
Subject: Re: revised heapsort
Message-ID: <29414@iuvax.cs.indiana.edu>
Date: 10 Nov 89 15:02:35 GMT
References: <110@bohra.cpg.oz>
Reply-To: rawlins@iuvax.cs.indiana.edu (Gregory J. E. Rawlins)
Organization: Dept. of Computer Science, Indiana University
Lines: 9

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.