Path: 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: 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") In article , 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