#Lara Pudwell
#Math 587
#1/24/05 -- heapsort

Help:=proc():
print('BuildHeap(L), Heapify(L), HSort(L)'):
end:

#BuildHeap(L) inputs a list of length L and sorts it into a Heap
#by repeated use of "Heapify"
BuildHeap:=proc(L) local i, L2:
L2:=L:

for i from nops(L2) by -1 to 1 do 
 L2:=[op(1..i-1,L2),op(Heapify([op(i..nops(L2),L2)], i))]:
od:

return(L2):
end:

#Heapify: inputs a list L and integer i and moves the root of L so that
#it has no children larger than itself
#(via repeatedly trading the root with its largest child)
#with the convention that L[1] is in array position i
#in a larger list being heapified
#e.g. Heapify([2,3,8,1,4,9,11,13],1) returns [8,3,11,1,4,9,2,13]
#whereas Heapify([2,3,8,1,4,9,11,13], 3) returns [4,3,8,1,2,9,11,13]
Heapify:=proc(L,i) local n, l, r, max, min:
n:=nops(L):

if(nops(L)<2*i-i+1) then return(L):

elif (nops(L)=2*i-i+1) then 
 if L[2*i-i+1]>L[1] then return([L[2*i-i+1],op(2..2*i-i,L),L[1]]):
 else return(L):
 fi:

else
l:=L[2*i-i+1]: r:=L[2*i+1-i+1]:
if(l>r) then max:=2*i-i+1: else max:=2*i+1-i+1: fi:
 if(L[max]>L[1]) then
     return([L[max],op(2..max-1,L),op(Heapify([L[1],op(max+1..n, L)], i+max-1))]):
 else
     return(L):
 fi:
fi:
end:


#HSort(L): inputs a list L of numbers, sorts them with the HeapSort Algorithm,
#and returns the sorted list
HSort:=proc(L) local i, L2:
L2:=BuildHeap(L):

 for i from nops(L2) by -1 to 2 do
	L2:=[op(Heapify([L2[i],op(2..i-1, L2)], 1)), L2[1], op(i+1..nops(L2),L2)]:
 od:
return(L2):
end: