Path: utzoo!utgpu!jarvis.csri.toronto.edu!mailrus!cornell!stefan
From: stefan@svax.cs.cornell.edu (Kjartan Stefansson)
Newsgroups: comp.theory
Subject: Re: Repost of "Revised Heapsort" requested
Message-ID: <34735@cornell.UUCP>
Date: 1 Dec 89 01:06:07 GMT
References: <3704@eagle.wesleyan.edu> <118@bohra.cpg.oz> <74578@tut.cis.ohio-state.edu>
Sender: nobody@cornell.UUCP
Reply-To: stefan@svax.cs.cornell.edu (Kjartan Stefansson)
Organization: Cornell Univ. CS Dept, Ithaca NY
Lines: 45
Summary: So, here it is.

In article <74578@tut.cis.ohio-state.edu> Jeff Martens <martens@cis.ohio-state.edu> writes:
>In article <118@bohra.cpg.oz> ejp@bohra.cpg.oz (Esmond Pitt) writes:
>>In article <3704@eagle.wesleyan.edu> aliao@eagle.wesleyan.edu writes:
>
>>>The 13 Nov. 89 posting about revised heapsort seems not to have made it to
>>>Wesleyan's Vax - could someone repost it?  Thanks.	-drew

(and others asking for the same)

Im' afraid the original article didn't have any brandnew theoretical
results, but anyway, here are the two articles that most people seemed
to have missed:

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.
>
>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

This is a reply from rawlins@iuvax.cs.indiana.edu (Gregory J. E. Rawlins):
>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.
>

Kjartan.


Brought to you by Super Global Mega Corp .com