[Home]  [Edit this page]  [Recent Changes]  [Special Pages]  [Help] 

---

HeapSort

---

(Computer science) Heap sort

Algorithm Analysis

The Heap Sort is one of the O(n log n) sorting algorithms. Unlike the Quick and Merge sorts it doesn't require recursions. In general Heap Sort is slower than Quick and Merge sorts, but it is the best at sorting the huge sets of items because it doesn't use recursions. Also if the array is partially sorted Heap Sort generally performs mush better than the Quick Sort.

The Heap Sort works as it name suggests. First it transforms a given array into a binary heap, and sets the heap length to the length of the starting array. Then it swaps the 1st and last element of the heap, reduces the length of the heap by one and pushes the first element down the tree as long as at least one of it's children is greater than him. The process is repeated until the length of a heap is reduced to 2.

Advantages: Doesn't use recursions.
Disadvantages: Slower than Quick and Merge sorts.

Source Code

Type
   TNumbers=Array[1..MaxInt] of Integer;
Procedure Swap(Var A,B:Integer);
Begin
   A:=A+B;
   B:=A-B;
   A:=A-B;
End;
Procedure FormHeap(N:Integer; Var X:TNumbers);
Var
   I,J:Integer;
Begin
   For I:=2 to N do
      Begin
         J:=I;
         While (X[J Div 2]<X[J]) And (J>1) do
            Begin
               Swap(X[J Div 2],X[J]);
               J:=J Div 2;
            End;
      End;
End;
Procedure HeapSort(N:Integer; Var X:TNumbers);
Var
   I,J:Integer;
   First,Max:Integer;
Begin
   FormHeap(N,X);
   For I:=N downto 2 do
      Begin
         Swap(X[1],X[I]);
         Max:=1;
         Repeat
            First:=Max;
            If (X[Max]<X[2*First]) And (2*First<I) then Max:=2*First;
            If (X[Max]<X[2*First+1]) And (2*First+1<I) then Max:=2*First+1;
            If First<>Max then Swap(X[First],X[Max]);
         Until First=Max;
      End;
End;

Visit http://www.goto-site.com/fnet/Pages/HeapSort.html for more info.
[Edit this page]  [Page history]  [What links here]  [Discuss this topic]  [Printer Friendly]