Struktur
data heap adalah sebuah objek array yang dapat dengan mudah divisualisasikan
sebagai complete tree. Ada korespondensi satu ke satu diantara elemen array dan
node dari tree. tree itu benar-benar penuh pada semua tingkatan kecuali mungkin
yang terendah, yang diisi dari kiri sampai titik tertentu. Semua node dari heap
juga memenuhi hubungan bahwa nilai kunci pada setiap node pada kurangnya sama
besar dengan nilai pada anak-anaknya.
Ini
dapat dilihat sebagai sebuah pohon biner dengan dua kendala tambahan:
- · Bentuk property : pohon itu adalah complete binary tree , yaitu semua tingkat tree, kecuali mungkin yang terakhir (paling dalam) sepenuhnya diisi, dan, jika tingkat terakhir tree itu tidak lengkap, maka node pada tingkat itu diisi dari kiri ke kanan.
- · Sifat heap: setiap node lebih besar dari atau sama dengan masing-masing anak sesuai dengan perbandingan predikat yang ditetapkan untuk struktur data.
Setiap
strategi menentukan sifat-sifat pohon dan nilainya. Jika Anda memilih strategi
min heap maka setiap ‘parent node’ akan memiliki nilai ≤ daripada ‘children’.
Misalnya, node pada root pohon akan memiliki nilai terkecil di pohon.
Kebalikannya ‘true’ untuk heap max strategi. Dalam pembahasan kita kali ini
kita harus mengasumsikan bahwa heap menggunakan strategi min heap kecuali
dinyatakan lain.
Tidak
seperti struktur data pohon lainnya, sebuah heap umumnya diimplementasikan
sebagai array, bukan serangkaian node yang masing-masing memiliki referensi ke
node lain. Simpul secara konseptual sama, namun, memiliki paling banyak dua
children.
Jenis-
jenis heap : min, max, min max heap.
Insert
Untuk
menambahkan sebuah element ke HEAP kita harus melakukan operasi up-heap (juga
dikenal sebagai bubble-up, percolate-up, sift-up, heapify-up, atau cascade-up)
untuk mengembalikan sifat heap. Kita dapat melakukan ini dalam O (log n) time,
menggunakan binary heap, dengan mengikuti algoritma ini:
- · Tambahkan elemen pada level bawah heap.
- · Bandingkan elemen yg baru ditambahkan dengan parentnya, jika mereka berada di urutan yang benar, berhenti.
- · Jika tidak, swap elemen dengan parent dan kembali ke langkah sebelumnya. Kita melakukan ini maksimum sekali untuk masing-masing tingkat di ketinggian tree, yang adalah O (log n). Namun, karena sekitar 50% dari elemen adalah leaves dan 75% berada di dua level di bawah, kemungkinan bahwa unsur baru yang akan dimasukkan hanya akan berpindah beberapa level ke atas untuk mempertahankan heap. Dengan demikian, binary heap mendukung insertion rata-rata dalam waktu yang konsta, O.
A. Jika min heap (elemen terkecil terletak
di root):
- · Maka yang dihapus merupakan rootnya(elemen terkecil).
- · Root yang dihapus tersebut kemudian digantikan oleh data terakhir di nodenya, kemudian data tersebut di downheapmin(jika anak < data tsb, maka tukar,dst sampai mentok dibawah atau node tsb<anaknya).
B. Jika max heap(elemen terkecil terletak di
root):
- · Maka yang dihapus merupakan rootnya(elemen terbesar).
- · Root yang dihapus tersebut kemudian digantikan oleh data terakhir di nodenya, kemudian data tersebut di downheapmax(jika anak > data tsb, maka tukar,dst), sampai mentok dibawah atau node tsb>anaknya).
Comments
Post a Comment