Struktur Data : Heap

Heap adalah salah satu dari struktur tree, heap digunakan pada algoritma pengurutan yang disebut heapsort. Heapsort dibandingkan dengan algoritma bubble sort dan quick sort. Misalnya H adalah pohon biner yang lengkap dengan N elemen ( dengan asumsi bahwa H terdapat pada memori dengan tree array linear menggunakan representasi sekuensial dari H, bukan representasi link.) Maka H disebut heap. Jenis dari heap adalah maxheap, dimana setiap nilai N lebih besar atau sama dengan nilai dari cabang N. Minheap dimana nilai N lebih kecil atau sama dengan nilai dari cabang N .

Umpamakan heap diatas adalah H, berarti elemen terbesar H terletak di paling atas heap, dimana :

Anggota	Urutan
25	1
13	2
17	3
5	4
8	5
3	6

Tabel diatas menggambarkan representasi dari H.

Memasukkan Elemen Baru

Umpamakan kita akan menyisipkan elemen baru, pada heap H, maka dilakukan prosedur sebagai berikut. :

1) Carilah posisi kosong pada successor, pada kasus ini ditemukan tempat kosong pada successor kanan,lalu tempatkan elemen baru tersebut pada posisi tersebut.

2) Lalu bandingkan elemen tersebut dengan parentnya, jka elemen tersebut lebih besar daripada parentnya, maka posisi parent dan elemen baru ditukarkan. Proses tersebut dilakukan terus menerus hingga nilai elemen lebih kecil daripada parent lalu posisi elemen baru dapat ditetapkan

            Contohnya kita akan membangun heap H dengan elemen sebagai berikut :

44, 30, 50, 22, 60, 55, 77, 55

Ini dapat dilakukan dengan cara memasukkan elemen-elemen tersebut satu persatu dengan cara menyisipkan kedalam heap H dengan prosedur diatas, seperti pada gambar :

Statement pengisian adalah sebagai berikut

INSHEAP(TREE, N, ITEM)  

- Heap H dengan N elemen terdapat pada array TREE dan info mengenai ITEM sudah ada. Prosedur ini memasukkan ITEM sebagai elemen baru dari H. PTR menunjukkan lokasi ITEM pada tree dan PAR menunjukkan lokasi dari parent ITEM

1. { Tambahkan node baru pada H dan inisialisasi PTR }

       Set N : = N + 1 dan PTR : = N

2. { Temukan lokasi untuk memasukkan ITEM }

Ulangi langkah 3 sampai 6 saat PTR < 1

3. Set PAR : = [ PTR/2 ] { Lokasi dari parent node }

4. If  ITEM  <= TREE [ PAR ], then :

                TREE [ PTR ] : = ITEM, dan return

              [ Akhir dari struktur if ]

5. Set TREE[ PTR ] : = TREE [ PAR ] { Turunkan node }

6. Set PTR : = PAR [ Update PTR ]

      [ Penutup langkah loop 2 ]

7. [ Tandai ITEM adalah akar dari H ]

Set TREE [1] : = ITEM

8. Return

Melihat bahwa ITEM tidak ditandai untuk sebuah elemen array TREE sampai tempat ITEM ditemukan. Langkah 7 dikhususkan untuk kasus dimana ITEM dinaikkan menjadi akar dari TREE[1]. Misal diberikan suatu array A  dengan N elemen . Dengan mengulang prosedur diatas pada A maka mengeksekusi dengan :

Call INSHEAP ( A,J,A(J+1))

Untuk J = 1, 2, ...., N -1, kita dapat membangun heap H keluar dari array A.

Menghapus akar dari suatu heap

Umpamakan H adalah sebuah heap dengan N elemen, dan diumpamakan kita ingin menghapus akar R dari H, langkah – langkahnya meliputi :

1) Tandai akar R menjadi beberapa variasi ITEM

2) Timpa node R yang dihapus dengan node R teraskhir dari H, sehingga
H masih merupakan TREE yang lengkap, tetapi bukan merupakan suatu heap

3) (Reheap) Biarkan L turun kebawah permukaan menuju tempat yang sesuai di H sehingga H akhirnya membentuk sebuah heap.

Berdasarkan heap H dimana R=95 yang merupakan root dan L=22 yang merupakan node terakhir dari tree. Langkah pertama dari prosedur diatas adalah menghapus R=95, dan langkah kedua menimpa R=95 dengan L=22. Ini menjadikannya suatu tree yang lengkap yang bukan merupakan suatu heap. Walaupun subtree kiri dan subtree kanan adalah 22 masih merupakan suatu heap. Langkah ketiga menemukan tempat yang tepat untuk 22 di dalam heap. Langkah-langkahnya sebagai berikut :

a) Bandingkan 22 dengan dua anaknya, 85 dan 70. karena 22 lebih kecil daripada anaknya, 85, maka 22 dan 85 ditukar posisinya.

b) Bandingkan 22 dengan dua anak barunya, 55 dan 33 karena 22 lebih kecil daripada 55 maka posisi 22 dan 55 ditukar.

c) Bandingkan 22 dengan anak barunya lagi, 15 dan 20. karena 20 lebih besar daripada kedua anak maka node 22 telah menempati posisi yang sesuai di H.

Prosedur menghapus heap :

DELHEAP(TREE,N,ITEM)

Sebuah heap H dengan N elemen disimpan dalam suatu array tree. Prosedur ini menandai TREE[1] root dari H ke ITEM yang bervariasi, lalu mengheapkan kembali elemen-elemen sebelumnya.

1. Set ITEM : = TREE[1].[ Pindahkan root dari H ]

2. Set LAST : =  TREE[N] dan N := N-1.[ Memindahkan node terakhir dari  H]

3. Set PTR :=1,LEFT :=2 dan RIGHT:=3 [ Inisialisasi pointer ]

4. Ulangi langkah ke 5 sampai 7 ketika RIGHT <= N:

5. If LAST >= TREE [LEFT] dan LAST >= TREE [ RIGHT], maka :            

      Set TREE[PTR]=LAST dan RETURN.[Akhir dari struktur if ]

6. If TREE[RIGHT]<=TREE[LEFT], maka :

Set TREE[PTR] :=TREE[LEFT] dan PTR := LEFT.

Else :

Set TREE[PTR]:=TREE[RIGHT] dan PTR:=RIGHT.[Akhir dari struktur if ]

7. Set LEFT:=2*PTR dan RIGHT:=LEFT+1

8. if LEFT=N dan if LAST<TREE[LEFT], maka :

Set PTR:=LEFT

9. Set TREE[PTR]:=LAST

10. Return

Heap Sort

Berdasarkan sebuah array A dengan N elemen yang diberikan. Algoritma Heap Sort untuk mengurutkan A terdiri dari dua fase, yaitu:

1) Fase A buat sebuah Heap A keluar dari elemen A.

2) Fase B: dengan cara mengulang hapus elemen root dari H.

Sejak akar dari H selalu mengandung node terbesar di H, fase B menghapus elemen di H dalam discrosing order. Source code algoritmanya adalah sebagai berikut:

void heapSort(int numbers[], int array_size)

{

  int i, temp;

  for (i = (array_size / 2)-1; i >= 0; i--)

    siftDown(numbers, i, array_size);

  for (i = array_size-1; i >= 1; i--)

  {

    temp = numbers[0];

    numbers[0] = numbers[i];

    numbers[i] = temp;

    siftDown(numbers, 0, i-1);

  }

}

void siftDown(int numbers[], int root, int bottom)

{

  int done, maxChild, temp;

  done = 0;

  while ((root*2 <= bottom) && (!done))

  {

    if (root*2 == bottom)

      maxChild = root * 2;

    else if (numbers[root * 2] > numbers[root * 2 + 1])

      maxChild = root * 2;

    else

      maxChild = root * 2 + 1;

    if (numbers[root] < numbers[maxChild])

    {

      temp = numbers[root];

      numbers[root] = numbers[maxChild];

      numbers[maxChild] = temp;

      root = maxChild;

    }

    else

      done = 1;

  }

}

Adapun pendapat lain tentang implementasinya dalam algoritma adalah sebagai berikut:

1  subtype index is positive range 1..N;

 2  type sort_array is array(index) of integer;

 3

 4  procedure heapsort (arr: in out sort_array)

 5  is

 6      N: index := arr'LENGTH;

 7      t: integer;

 8  

 9      procedure siftdown (N, k: index)

10      is

11          j: index;

12          v: integer;

13          w: integer;

14      begin

15          v := arr(k); w := k;

16          discrete h := k in 1..N/2

17              new h := 2*h | 2*h+1

18          loop

19              j := 2*h;

20              if j < N and then arr(j) < arr(j+1) then

21                  j := j+1;

22              end if;

23              if v >= arr(j) then

24                  w := h;  -- save h for writing back (line 31)

25                  exit;

26              end if;

27              arr(h) := arr(j);

28              h := j;

29              w := h;  -- save h for writing back (line 31)

30          end loop;

31          arr(w) := v;

32      end siftdown;

33  

34  begin

35

36      -- construct the heap

37

38      for k in reverse 1..N/2 loop

39          siftdown (N, k);

40      end loop;

41

42      -- remove elements in descending order

43

44      for M in reverse 2..N loop

45          t := arr(1);

46          arr(1) := arr(M);

47          arr(M) := t;

48          siftdown ((M-1), 1);

49      end loop;

50  end heapsort;