HEAP

Pengertian Heap Adalah struktur data yang berbentuk pohon yang memenuhi sifat-sifat heap yaitu jika B adalah anak dari A, maka nilai yang tersimpan di simpul A lebih besar atau sama dengan nilai yang tersimpan di simpul B.

Hal ini mengakibatkan elemen dengan nilai terbesar selalu berada pada posisi akar, dan heap ini disebut max heap.

(Bila perbandingannya diterbalikkan yaitu elemen terkecilnya selalu berada di simpul akar, heap ini disebut adalah min heap).

Karena itulah, heap biasa dipakai untuk mengimplementasikan priority queue. Operasi-operasi yang digunakan untuk heap adalah:

• Delete-max atau delete-min: menghapus simpul akar dari sebuah max atau min heap.

• Increase-key atau decrease-key: mengubah nilai yang tersimpan di suatu simpul.

• Insert: menambahkan sebuah nilai ke dalam heap.

• Merge: menggabungkan dua heap untuk membentuk sebuah heap baru yang berisi semua elemen pembentuk heap tersebut.

.2 Jenis-jenis Heap

.2.1 Binary heap

adalah heap yang dibuat dengan menggunakan pohon biner.

.2.2 Binomial heap

adalah heap yang dibuat dengan menggunakan pohon binomial.

Pohon binomial bila didefinisikan secara rekursif adalah:

• Sebuah pohon binomial dengan tinggi 0 adalah simpul tunggal

• Sebuah pohon binomial dengan tinggi k mempunyai sebuah simpul akar yang anak-anaknya adalah akar-akar pohon pohon binomial.

.2.3 Fibonacci Heap

Fibonacci heap adalah kumpulan pohon yang membentuk minimum heap.

Pohon dalam struktur data ini tidak memiliki bentuk yang tertentu dan pada kasus yang ekstrim heap ini memiliki semua elemen dalam pohon yang berbeda atau sebuah pohon tunggal dengan tinggi Keunggulan dari Fibonacci heap adalah ketika menggabungkan heap cukup dengan menggabungkan dua list pohon.

Heap Sort

HeapSort adalah algoritma pengurutan data berdasarkan perbandingan, dan termasuk golongan selection sort.

Walaupun lebih lambat daripada quick sort pada kebanyakan mesin , tetapi heap sort mempunyai keunggulan yaitu kompleksitas algoritma pada kasus terburuk adalah n log n.

Algoritma pengurutan heap sort ini mengurutkan isi suatu larik masukan dengan memandang larik masukan sebagai suatu Complete Binary Tree (CBT).

Setelah itu Complete Binary Tree (CBT) ini dapat dikonversi menjadi suatu heap tree. Setelah itu Complete Binary Tree (CBT) diubah menjadi suatu priority queue.

Algoritma pengurutan heap dimulai dari membangun sebuah heap dari kumpulan data yang ingin diurutkan, dan kemudian menghapus data yang mempunyai nilai tertinggi dan menempatkan dalam akhir dari larik yang telah terurut.

Setelah memindahkan data dengan nilai terbesar, proses berikutnya adalah membangun ulang heap dan memindahkan nilai terbesar pada heap tersebut dan menempatkannya dalam tempat terakhir pada larik terurut yang belum diisi data lain.

Proses ini berulang sampai tidak ada lagi data yang tersisa dalam heap dan larik yang terurut penuh. Dalam implementasinya kita membutuhkan dua larik – satu untuk menyimpan heap dan satu lagi untuk menyimpan data yang sudah terurut.

Tetapi untuk optimasi memori, kita dapat menggunakan hanya satu larik saja.

Yaitu dengan cara menukar isi akar dengan elemen terakhir dalam heap tree.

Jika memori tidak menjadi masalah maka dapat tetap menggunakan dua larik yaitu larik masukan dan larik hasil.

Heap Sort memasukkan data masukan ke dalam struktur data heap.

Nilai terbesar (dalam max-heap) atau nilai terkecil (dalam min-heap) diambil satu per satu sampai habis, nilai tersebut diambil dalam urutan yang terurut.

Algoritma untuk heap sort :

function heapSort(a, count) is

input: sebuah larik tidak terurut a dengan panjang length

(pertama letakkan a dalam max-heap) heapify(a, count)

end := count -1

while end > 0 do

remove ( )

reheapify ( )

end := end – 1

Heap itu sebenarnya lebih "nikmat" menggunakan array biasa dibanding pakai struct atau apalah itu. Soalnya, tiap data baru yang masuk, bakalan masuk di index paling bawah yang kosong. Jadi, penomoran indexnya, saya pakai contoh min heap di atas aja ya..

misalkan arraynya x. Maka:

x[1]=2;      x[4]=51;      x[7]=20;

x[2]=50;    x[5]=100;    dst

x[3]=4;      x[6]=10;

rumus:

Index_Parent=Index/2;

Index_Child_Kiri=Index*2;

Index_Child_kanan=Index*2+1;