Heap sort

Heap sort adalah sebuah metode sorting (pengurutan) angka pada sebuah array dengan cara menyerupai binary tree, yaitu dengan cara memvisualisasikan sebuah array menjadi sebuah binary tree yang nantinya pada binary tree tersebut nilai pada masing-masing index array akan diurutkan. Pada heap sort terdapat 3 bagian yaitu Node, Edge, dan leaf dimana node itu adalah setiap index yang berada pada array, edge adalah garis yang menghubungkan tiap node dan leaf adalah setiap node yang tidak memiliki child node (node turunan). Selain itu juga ada yang bernama root yaitu node awal pada sebuah heap.

Berikut contoh source code pada pascal :

program Heap ( input, infile, output ) ;
const
    NameLength = 30;
    ListLength = 100 ;
type
    FileName = String(NameLength);
    ListIndex = 1 .. ListLength;
    ListItem = integer;
    list = array [ListIndex] of ListItem;
var
    FName : FileName;
    infile : text;
    l: list;
    i : integer;
    size : integer ;
(*----------------------------------------------------------*)
procedure Swap ( var x,y : ListItem ) ;
    var
     Temp : ListItem ;  (* temp storage *)
    begin (* procedure *)
         Temp := x;
         x:= y;
         y:= Temp;
    end  (* Swap *) ;
(*------------------------------------------------------------------*)
procedure FixHeap ( var a : List ; i : ListIndex ; Size : ListIndex );
    var
         j : ListIndex;
    begin (* procedure *)
         if i <= Size div 2 then begin
             j := 2*i;
             if j+1 <= Size then begin
                  if a[j] < a[j+ 1] then begin
                      j := j+1;
                  end;
             end ;
             if a[i] < a[j] then begin
                  Swap (a[j],a[i] ) ;
                  fixheap (a, j, Size) ;
             end ;
         end ;
    end  (* FixHeap *) ;
(*----------------------------------------------------------*)

procedure MakeHeap
    ( var A : List ; Size : ListIndex ) ;
    var
     i : integer ;  (* lcv *)
    begin (* procedure *)
         for i := Size div 2 downto 1 do begin
           FixHeap(A,i,Size);
         end  (* loop *) ;
    end  (* MakeHeap *) ;
(*==================================================================*)
begin (* main program *)
    WriteLn ('what file?');
    ReadLn(FName);
    Open (infile, fname, old);
    Reset(infile);
    i := 1;
    while not eof (infile) do begin
         ReadLn(infile, L[i]) ;
         i := i+1;
    end ;
    Size := i - 1 ;
    WriteLn ( 'Unsorted Data:');
    for i := 1 to Size do begin
         Write (L[i]:7);
         if i mod 10 = 0 then begin
             WriteLn ;
         end ;
    end;
    WriteLn ;
    MakeHeap(L, Size);
    for i := Size downto 2 do begin
      Swap (L[i],L[1]) ;
      Fixheap(L, 1,i-1);
    end  (* loop *) ;
    WriteLn ('Sorted Data:');
    for i := 1 to Size do begin
      Write(L[i]:7);
      if i mod 10 = 0 then begin
         writeln;
      end  (* if *) ;
    end  (* loop *) ;
    Close (infile) ;
end (* Heap *).

Berikut contoh dalam bentuk gif :

Sumber : Loserbombti, Scranton