Heapsort FixHeap Code

FixHeap(StartVertex)

v := StartVertex;

while 2*v ? n do

LargestChild := 2*v;

if 2*v < n then

if L[2*v] < L[2*v+1] then

LargestChild := 2*v+1;

endif

if L[v] < L[LargestChild] Then

Exchange(L[v],L[LargestChild]);

v := LargestChild

else

v := n;

endif

endwhile

end FixHeap

n is the size of the heap

Worst case run time is

?(lg n)