Sruktur data heap

Struktur Data Heap: Pengertian, Karakteristik, dan Operasinya

Oleh Trivusi Diperbarui: 07 Januari 2023 Posting Komentar

Heap diketahui merupakan struktur data yang sangat berguna dan diperlukan baik oleh setiap programmer. Struktur data heap digunakan dalam heap sort dan antrian prioritas.

Di blog ini, kita akan membahas lebih lanjut mengenai pengertian, karakteristik, dan operasi-operasi yang ada pada struktur data heap. Yuk, simak!

Adapun jenis-jenis heap property di antaranya :

Max-Heap: Kunci atau nilai yang ada di simpul mana pun harus lebih besar dari kunci/nilai yang ada di kedua simpul anaknya. Kunci terbesar ada di simpul akar (root node).

Pengertian Struktur Data Heap

Heap adalah struktur data berbentuk pohon biner lengkap yang memenuhi properti heap.

Struktur Data Heap: Pengertian, Karakteristik, dan Operasinya

Pohon biner lengkap sendiri dapat didefinisikan sebagai pohon biner di mana semua level terisi penuh, kecuali level terakhir. Semua kunci atau nilai pada level terakhir harus rata kiri jika tidak terisi penuh.Adapun jenis-jenis heap property di antaranya:

Max-Heap: Kunci atau nilai yang ada di simpul mana pun harus lebih besar dari kunci/nilai yang ada di kedua simpul anaknya. Kunci terbesar ada di simpul akar (root node).Min-Heap: Kunci yang ada di simpul mana pun harus lebih kecil dari kunci yang ada di kedua anaknya. Kunci terkecil ada di simpul akar.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.