Sabtu, 25 Mei 2013

Heap Java

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.

 
Jenis-jenis heap:

Min Heap  : Nilai setiap node lebih kecil dari anak-anaknya
Contoh Min Heap:



Max Heap : Nilai setiap node lebih besar dari anak-anaknya
Operasi-operasi yang digunakan untuk heap adalah:
  1. Delete-max atau delete-min: menghapus simpul akar dari sebuah max atau min heap.  
  2. Increase-key atau decrease-key: mengubah nilai yang tersimpan di suatu simpul. 
  3. Insert: menambahkan sebuah nilai ke dalam heap.  
  4. Merge: menggabungkan dua heap untuk membentuk sebuah heap baru yang berisi semua elemen pembentuk heap tersebut. 

Implementasi pada array:

  1. Unsur-unsur disimpan berurutan dari indeks 1 sampai N dari atas ke bawah dan dari kiri ke kanan node pohon.
  2. Root disimpan dalam indeks 1 (kita membiarkan indeks 0 menjadi kosong / tidak terpakai).

Representasi array:




Memasukkan Min-Heap
• Masukkan unsur baru pada akhir heap
• Naikkan heap baru/angka yang perlu dinaikkan

Penghapusan pada Min-Heap
• Perhatikan penghapusan elemen terkecil yang terletak pada akar.
 Ganti root dengan elemen terakhir dari heap
• Penurunan jumlah elemen dalam tumpukan
• Memperbaiki properti heap nya

Min-Max Heap
• Kondisi tumpukan bergantian antara tingkat minimum dan maksimum untuk tingkat
Tujuan min-max tumpukan adalah untuk memungkinkan kita untuk menemukan keduaelemen terkecil 
   dan terbesar dari tumpukan pada waktu yang sama. 

Penghapusan pada Min-Max Heap
• Penghapusan elemen terkecil:
  - 
Ganti root dengan elemen terakhir dalam tumpukan.
  - 
Penurunan jumlah elemen dalam tumpukan.
  - 
Downheapmin dari root.

• Penghapusan elemen terbesar:
  - 
Ganti anak kiri atau kanan-anak dari akar (tergantung pada mana yang lebih besar) dengan elemen
     terakhir dalam tumpukan.
  -
 Penurunan jumlah elemen dalam tumpukan.
  - 
Downheapmax dari node.



Tidak ada komentar:

Posting Komentar