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.