aliao@eagle.wesleyan.edu (11/17/89)
The 13 Nov. 89 posting about revised heapsort seems not to have made it to Wesleyan's Vax - could someone repost it? Thanks. -drew
ejp@bohra.cpg.oz (Esmond Pitt) (11/20/89)
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 It didn't make it to me either, and as I asked the original question I'd like a repost too please ... Alternatively could somebody mail it to me. Tks. -- Esmond Pitt, Computer Power Group ejp@bohra.cpg.oz
martens@ketch.cis.ohio-state.edu (Jeff Martens) (12/01/89)
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 >It didn't make it to me either, and as I asked the original question >I'd like a repost too please ... Alternatively could somebody mail it >to me. Tks. Well, I missed it too, so if someone could repost it or send me a copy, I'd appreciate it. Thanks. -=- -- Jeff (martens@cis.ohio-state.edu) With the 11/89 issue, the Communications of the ACM has finally become 100% devoid of computer science.
stefan@svax.cs.cornell.edu (Kjartan Stefansson) (12/01/89)
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.
rawlins@iuvax.cs.indiana.edu (Gregory J. E. Rawlins) (12/01/89)
In article <34735@cornell.UUCP> stefan@svax.cs.cornell.edu (Kjartan Stefansson) writes:
[four articles and requests]
I don't know why this keeps coming up, i don't remember heapsort being
discussed in this newsgroup in the recent past. Anyway, beside the Gonnet
and Munro paper (SIAM J. Comp. 15,964-971) you may want to look for Svante
Carlsson's 1986 thesis _Heaps_, Doctoral Dissertiation, Department of Computer
Science, Lund University, Lund, Sweden. Also, Svante, Ian, and Patricio
Poblete have a paper in SWAT on constant time implicit heap insertion
(Carlsson, Munro, and Poblete, ``An Implicit Binomial Queue with Constant
Insertion Time,'' First Scandinavian Workshop on Algorithm Theory,
Halmstad, Sweden, Springer-Verlag LNCS 318.
gregory.