Path: utzoo!attcan!utgpu!jarvis.csri.toronto.edu!mailrus!wuarchive!gem.mps.ohio-state.edu!tut.cis.ohio-state.edu!ucbvax!UKANVAX.BITNET!MARKV
From: MARKV@UKANVAX.BITNET ("MARK GOODERUM - UNIV. OF KANSAS ACS - MARKV@UKANVAX")
Newsgroups: comp.lang.modula2
Subject: Re: Quicksort vs. Heapsort
Message-ID: <INFO-M2%89100509454230@UCF1VM>
Date: 5 Oct 89 13:42:00 GMT
Sender: daemon@ucbvax.BERKELEY.EDU
Reply-To: Modula2 List <INFO-M2%UCF1VM.BITNET@PSUVM.PSU.EDU>
Organization: The Internet
Lines: 12

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.

Ohh, shoot.  Emergency, gotta go, sorry.  Anyone want to pick up where I left
off?

-Mark Gooderum