Struktur Data Heap

 Struktur Data Heap: Pengertian, Karakteristik, dan Operasinya

Heap merupakan struktur data yang sangat berguna dan perlu diketahui dengan baik oleh setiap programmer. Struktur data heap digunakan dalam heap sort dan priority queue.

Pengertian Struktur Data Heap

Heap adalah struktur data berbentuk complete binary tree yang memenuhi heap property.
Complete binary tree sendiri dapat didefinisikan sebagai binary tree di mana semua level terisi penuh, kecuali level terakhir. Semua kunci atau nilai pada level terakhir harus rata kiri apabila 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.

Karakteristik Struktur Data Heap


Heap memiliki ciri-ciri sebagai berikut:

Sistem menetapkan heap identifier unik untuk setiap heap dalam grup aktivasi. Heap identifier untuk heap default selalu bernilai nol. API bindable manajemen penyimpanan, dipanggil oleh program atau prosedur, menggunakan heap identifier untuk mengidentifikasi heap yang akan digunakan untuk bertindak. API bindable harus dijalankan dalam grup aktivasi yang memiliki heap.
Ukuran heap diperluas secara dinamis untuk memenuhi permintaan alokasi. Ukuran maksimum heap adalah (4GB – 512KB). Ukuran tersebut adalah ukuran heap maksimum jika jumlah total alokasi (pada satu waktu) tidak melebihi 128.000.
Ukuran maksimum alokasi tunggal apa pun dari heap dibatasi hingga (16MB – 64KB).

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.

Komentar

Posting Komentar

Postingan populer dari blog ini

Pengertian Algoritma Pencarian

 Algoritma Pencarian: Pengertian, Karakteristik, dan Jenis-Jenisnya Algoritma pencarian merupakan salah satu area yang penting dalam    ilmu  komputer khususnya bidang    kecerdasan buatan . Pengertian Algoritma Pencarian Dalam ilmu komputer, algoritma pencarian adalah algoritma yang dirancang untuk memecahkan masalah pencarian. Algoritma pencarian bekerja untuk mengambil informasi yang disimpan dalam struktur data tertentu, atau dihitung dalam ruang pencarian domain masalah, baik dengan nilai diskrit atau kontinu. Algoritma pencarian berupa prosedur langkah demi langkah yang digunakan untuk menemukan data tertentu di antara kumpulan data. Algoritma ini dapat dianggap sebagai metode mendasar dalam operasi komputasi. Ketika sebuah sistem mencari data, perbedaan antara aplikasi yang cepat dan yang lebih lambat seringkali terletak pada penggunaan algoritma pencarian yang tepat. Dalam kecerdasan buatan, teknik atau algoritma pencarian adalah metode pemecahan masalah yang universal. Istilah
Baca selengkapnya

FUNGSI DALAM MATEMATIKA

FUNGSI DALAM MATEMATIKA. Fungsi dalam istilah matematika merupakan pemetaan setiap anggota sebuah himpunan (dinamakan sebagai domain atau variabel bebas) kepada anggota himpunan yang lain (dinamakan sebagai kodomain atau variabel terikat) yang dapat dinyatakan dengan lambang{\displaystyle y=f(x)}, atau dapat menggunakan lambang {\displaystyle g(x)}, {\displaystyle P(x)}.[1][2] Istilah ini berbeda pengertiannya dengan kata yang sama yang dipakai sehari-hari, seperti “alatnya berfungsi dengan baik.” Konsep fungsi adalah salah satu konsep dasar dari matematika dan setiap ilmu kuantitatif. Istilah "fungsi", "pemetaan", "peta", "transformasi", dan "operator" biasanya dipakai secara sinonim.[3] Grafik contoh sebuah fungsi, {\displaystyle {\begin{aligned}&\scriptstyle \\&\textstyle f(x)={\frac {(4x^{3}-6x^{2}+1){\sqrt {x+1}}}{3-x}}\end{aligned}}} Baik domain maupun kisaran dalam gambar adalah himpunan bilangan riil di antara -1 dan 1,5
Baca selengkapnya

SISTEM BILANGAN KOMPUTER

SISTEM BILANGAN Desimal , Biner, Oktal dan Heksadesimal Tujuan : Setelah mempelajari Sistem Bilangan diharapkan dapat, 1. Memahami jenis-jenis sistem bilangan yang digunakan pada teknik mikroprosessor 2. Memahami konversi sistem bilangan desimal ke sistem bilangan biner 3. Memahami konversi sistem bilangan desimal ke sistem bilangan oktal 4. Memahami konversi sistem bilangan desimal ke sistem bilangan heksadesimal 5. Memahami konversi sistem bilangan biner ke sistem bilangan oktal atau sebaliknya 6. Memahami konversi sistem bilangan biner ke sistem bilangan heksadesimal atau sebaliknya 7. Memahami konversi sistem bilangan desimal dan sistem bilangan biner antara 0 dan 1 8. Mampu merubah bilangan desimal ke bentuk BCD atau sebaliknya 9. Mampu merubah bilangan desimal ke bentuk BCH atau sebaliknya 10. Memahami ASCII Code untuk pembentukan karakter Sistem Bilangan umum Dalam kehidupan sehari-hari, bilangan yang kita pergunakan untuk menghitung adalah bilangan yang berbas
Baca selengkapnya