Article View: comp.lang.modula2
Article #350Re: Quicksort vs. Heapsort
From: Piet van Oostrum
Date: Mon, 09 Oct 1989 16:01
Date: Mon, 09 Oct 1989 16:01
15 lines
1472 bytes
1472 bytes
In article <INFO-M2%89100509454230@UCF1VM>, MARKV@UKANVAX ("MARK GOODERUM - UNIV. OF KANSAS ACS - MARKV@UKANVAX") writes:
`A 'real' heapsort works in a heap. The easiest implementation to imagine
`is an array.
`
`Heapsort works on the principle of a partially ordered tree. For each element
`n, it's two children are stored as element 2n and 2n+1. The partailly ordered
`tree property states that every element n is greater than its left child 2n
`and less than its right child 2n+1.
`
No, <= both, or >=, depending on the direction of the sort.
--
Piet van Oostrum, Dept of Computer Science, University of Utrecht
Padualaan 14, P.O. Box 80.089, 3508 TB Utrecht, The Netherlands.
Telephone: +31-30-531806 Internet: piet@cs.ruu.nl
Telefax: +31-30-513791 Uucp: uunet!mcsun!hp4nl!ruuinf!piet
Technical Details
Message-ID:
<1677@ruuinf.cs.ruu.nl>Path:
arc1-ca.pugleaf.net!utzoo!attcan!utgpu!jarvis.csri.toronto.edu!mailrus!uwm.edu!uakari.primate.wisc.edu!gem.mps.ohio-state.edu!apple!bloom-beacon!eru!luth!sunic!mcsun!hp4nl!ruuinf!pietReferences:
<INFO-M2%89100509454230@UCF1VM>Show Full Headers
Complete Article Headers
Path: arc1-ca.pugleaf.net!utzoo!attcan!utgpu!jarvis.csri.toronto.edu!mailrus!uwm.edu!uakari.primate.wisc.edu!gem.mps.ohio-state.edu!apple!bloom-beacon!eru!luth!sunic!mcsun!hp4nl!ruuinf!piet
From: piet@cs.ruu.nl (Piet van Oostrum)
Newsgroups: comp.lang.modula2
Subject: Re: Quicksort vs. Heapsort
Message-ID: <1677@ruuinf.cs.ruu.nl>
Date: 9 Oct 89 16:01:07 GMT
References: <INFO-M2%89100509454230@UCF1VM>
Sender: news@ruuinf.cs.ruu.nl
Reply-To: piet@cs.ruu.nl (Piet van Oostrum)
Organization: Dept of Computer Science, University of Utrecht, Holland
Lines: 15
In-reply-to: MARKV@UKANVAX.BITNET ("MARK GOODERUM - UNIV. OF KANSAS ACS - MARKV@UKANVAX")