Struktur Data Heap: Pengertian, Karakteristik, dan Operasinya

 

• Struktur Data Heap: Pengertian, Karakteristik, dan Operasinya

• Deletion: Menghapus item dari heap.
• Extract Min-Max: Mengembalikan dan menghapus elemen maksimum atau minimum masing-masing di max-heap dan min-heap.

Heapify

Heapify adalah proses untuk mengatur ulang elemen heap untuk mempertahankan properti heap. Ini dilakukan ketika node tertentu menyebabkan ketidakseimbangan di heap karena beberapa operasi pada node tersebut.

Heapify dapat dilakukan dalam dua metodologi:

1. up_heapify()
   Metodologi heapify yang mengikuti pendekatan bottom-up. Kita akan memeriksa apakah node mengikuti properti heap dengan menuju ke arah rootNode atau tidak. Apabila tidak mengikuti, kita melakukan operasi tertentu agar tree mengikuti properti heap.
2. down_heapify()
   Kebalikan dari up heapify, dimana down heapify mengikuti pendekatan top-down.Kita memeriksa apakah node mengikuti properti heap dengan menuju ke arah node daun. Jika node tidak mengikuti properti heap, kita melakukan operasi tertentu agar tree mengikuti properti heap.

Find-max (atau Find-min)

Elemen maksimum dan elemen minimum di max-heap dan min-heap ditemukan di simpul akar (root node) dari heap.

Insertion

Operasi insertion pada heap mengikuti langkah-langkah berikut

• Sisipkan elemen baru di ujung heap.
• Karena elemen yang baru dimasukkan dapat mendistorsi properti Heap. Jadi, kita perlu melakukan operasi up_heapify() , untuk menjaga properti heap dalam pendekatan bottom-up.

Deletion

Operasi deletion atau penghapusan standar pada heap adalah menghapus elemen yang ada di simpul akar heap. Operasi deletion mengikuti langkah berikut:

• Ganti elemen yang akan dihapus oleh elemen terakhir di heap.
• Hapus item terakhir dari heap.
• Sekarang, elemen terakhir ditempatkan pada beberapa posisi di heap, dimana ada kemungkinan tree tidak mengikuti properti heap, jadi kita perlu melakukan operasi down_heapify() untuk mempertahankan struktur heap. Operasi down_heapify() melakukan heapify dalam pendekatan top-bottom.

Extract Min-Max

Operasi ini mengembalikan dan menghapus elemen maksimum atau minimum masing-masing di max-heap dan min-heap. Elemen maksimum ditemukan di simpul akar.

Kegunaan Struktur Data Heap

• Heap digunakan untuk membuat antrian prioritas (priority queue).
• Heap sort adalah salah satu algoritma sorting tercepat dengan kompleksitas waktu O(N* log(N), dan mudah diimplementasikan.
• Best First Search (BFS) adalah teknik informed search, di mana teknik ini diimplementasikan menggunakan antrian prioritas yang dibuat dengan heap.

Kelebihan Struktur Data Heap

Struktur data heap memiliki keunggulan atau kelebihan sebagai berikut:

• Kompleksitas waktu pada struktur data heap cenderung lebih sedikit. Untuk memasukkan atau menghapus elemen di heap, kompleksitas waktunya hanya O(log N).
• Membantu untuk menemukan jumlah minimum dan jumlah terbesar.
• Untuk operasi peek elemen paling awal, kompleksitas waktunya konstan O(1).
• Dapat diimplementasikan menggunakan array, tidak memerlukan ruang ekstra untuk pointer.
• Binary heap adalah pohon biner yang seimbang, dan mudah diterapkan.
• Heap dapat dibuat dengan O(N) waktu.

Kekurangan Struktur Data Heap

Berikut ini adalah beberapa kekurangan dari struktur data heap:

• Kompleksitas waktu untuk mencari elemen di Heap adalah O(N).
• Untuk menemukan penerus atau pendahulu dari suatu elemen, heap membutuhkan waktu O(N), sedangkan BST hanya membutuhkan waktu O(log N).
• Untuk mencetak semua elemen heap dalam urutan kompleksitas waktu adalah O(N*log N), sedangkan untuk BST, hanya dibutuhkan waktu O(N).
• Manajemen memori lebih kompleks dalam tumpukan memori karena digunakan secara global. Memori heap dibagi menjadi dua bagian - generasi lama dan generasi muda dll. pada garbage collection milik java.

Penutup

Demikianlah penjelasan lengkap mengenai struktur data heap. Semoga informasi yang disajikan dapat bermanfaat dan menambah khazanah pengetahuan kita.