Struktur Data Heap

Heap adalah kasus khusus dari struktur data pohon biner yang seimbang di mana kunci root-node dibandingkan dengan turunannya dan disusun sesuai. Jikaα memiliki simpul anak β kemudian -

kunci (α) ≥ kunci (β)

Karena nilai induk lebih besar dari nilai anak, properti ini akan dihasilkan Max Heap. Berdasarkan kriteria ini, heap dapat terdiri dari dua jenis -

For Input → 35 33 42 10 14 19 27 44 26 31

Min-Heap - Dimana nilai dari simpul akar kurang dari atau sama dengan salah satu dari anak-anaknya.

Max-Heap - Di mana nilai dari simpul akar lebih besar dari atau sama dengan salah satu dari anak-anaknya.

Kedua pohon dibangun menggunakan masukan dan urutan kedatangan yang sama.

Algoritma Konstruksi Heap Maks

Kita akan menggunakan contoh yang sama untuk mendemonstrasikan bagaimana Max Heap dibuat. Prosedur untuk membuat Min Heap serupa tetapi kami menggunakan nilai min alih-alih nilai maks.

Kita akan mendapatkan algoritma untuk tumpukan maksimal dengan memasukkan satu elemen pada satu waktu. Kapan pun, heap harus mempertahankan propertinya. Saat penyisipan, kami juga mengasumsikan bahwa kami menyisipkan node di pohon yang sudah menumpuk.

Step 1 − Create a new node at the end of heap.
Step 2 − Assign new value to the node.
Step 3 − Compare the value of this child node with its parent.
Step 4 − If value of parent is less than child, then swap them.
Step 5 − Repeat step 3 & 4 until Heap property holds.

Note - Dalam algoritma konstruksi Min Heap, kami mengharapkan nilai node induk lebih kecil dari nilai node anak.

Mari kita pahami konstruksi Max Heap dengan ilustrasi animasi. Kami mempertimbangkan sampel input yang sama yang kami gunakan sebelumnya.

Algoritma Penghapusan Heap Maks

Mari kita turunkan algoritma untuk menghapus dari tumpukan maksimum. Penghapusan di Max (atau Min) Heap selalu terjadi di root untuk menghapus nilai Maksimum (atau minimum).

Step 1 − Remove root node.
Step 2 − Move the last element of last level to root.
Step 3 − Compare the value of this child node with its parent.
Step 4 − If value of parent is less than child, then swap them.
Step 5 − Repeat step 3 & 4 until Heap property holds.