Struktur Data Heap

 

Pengertian Struktur Data Heap

Heap adalah struktur data berbentuk complete binary tree yang memenuhi heap property.

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).

Operasi-operasi pada Struktur Data Heap

Operasi umum yang terlibat dalam heap di antaranya:

  • Heapify: Proses untuk mengatur ulang heap untuk mempertahankan properti heap.
  • Find-max (atau Find-min): Menemukan item maksimum dari max-heap, atau item minimum dari min-heap.
  • Insertion: Menambahkan item baru di heap.
  • Deletion: Menghapus item dari heap.
  • Extract Min-Max: Mengembalikan dan menghapus elemen maksimum atau minimum masing-masing di max-heap dan min-heap.

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.

Komentar

Posting Komentar

Postingan populer dari blog ini

Gambar
  PENGERTIAN GRAPH  JENIS DAN KEGUNAAN NYA Graph adalah jenis struktur data umum yang susunan datanya tidak berdekatan satu sama lain (non-linier). Graph terdiri dari kumpulan simpul berhingga untuk menyimpan data dan antara dua buah simpul terdapat hubungan saling keterkaitan. Sebagai contoh, terdapat graph seperti berikut: Sumber: programiz.com Graph di atas terdiri atas 4 buah verteks dan 4 pasang sisi atau edge. Dengan verteks disimbolkan sebagai V, edge dilambangkan E, dan graph disimbolkan G, ilustrasi di atas dapat ditulis dalam notasi berikut: V = {0, 1, 2, 3} E = {(0,1), (0,2), (0,3), (1,2)} G = {V, E} Graph banyak dimanfaatkan untuk menyelesaikan masalah dalam kehidupan nyata, dimana masalah tersebut perlu direpresentasikan atau diimajinasikan seperti sebuah jaringan. Jenis-jenis Graph Graph dapat dibedakan berdasarkan arah jelajahnya dan ada tidaknya label bobot pada relasinya. Berdasarkan arah jelajahnya graph dibagi menjadi  Undirected graph  dan  Directed graph . Fungsi d
Baca selengkapnya

Fungsi

FUNGSI Fungsi adalah istilah yang tentunya sudah tidak asing lagi di telinga kebanyakan orang. Fungsi merupakan istilah yang kerap digunakan dalam  percakapan  sehari-hari. Arti dari fungsi sendiri yaitu kegunaan suatu hal. Namun,  fungsi  juga ditemukan dalam berbagai bidang lainnya, salah satunya matematika. Menurut Kamus Besar Bahasa Indonesia (KBBI), dalam matematika, fungsi adalah besaran yang berhubungan, jika besaran yang satu berubah, besaran yang lain juga berubah. Fungsi adalah salah satu konsep dasar dari  matematika  dan setiap ilmu kuantitatif.  Fungsi Injektif Fungsi f: A → B disebut fungsi satu-satu atau fungsi injektif apabila setiap dua elemen yang berlainan di A akan dipetakan pada dua elemen yang berbeda di B. Jadi, bisa dikatakan kalau f:A→B adalah fungsi injektif apabila a ≠ b berakibat f(a) ≠ f(b) atau ekuivalen, jika f(a) = f(b) maka akibatnya a = b. Contoh: A = {1, 2, 3} B = {a, b, c} F: A => B {(1,a), (2,a), (3,b)}   2. Fungsi Surjektif Fungsi f: A → B diseb
Baca selengkapnya

Pengertian struktur data tree

  Pengertian Struktur Data Tree Tree adalah tipe  struktur data  yang sifatnya  non-linier  dan berbentuk  hierarki . Istilah-istilah pada Tree Layaknya sebuah pohon yang memiliki akar, cabang, dan daun yang terhubung satu sama lain, pada struktur data tree terdapat beberapa istilah penting yang mirip seperti istilah di dunia nyata, antara lain: 1. Node Node atau simpul adalah entitas pada struktur data tree yang mengandung sebuah nilai dan pointer yang menunjuk simpul di bawahnya (child node). 2. Child node Child node atau simpul anak adalah simpul turunan dari simpul di atasnya. 3. Leaf Node Leaf node atau simpul daun adalah simpul yang tidak memiliki child node dan merupakan node yang paling bawah dalam struktur data tree. Simpul ini biasa disebut juga sebagai external node Jenis-jenis Tree Struktur data tree dapat diklasifikasikan ke dalam 4 jenis, yaitu:  General tree ,  Binary tree ,  Balanced tree , dan  Binary search tree . 1. General tree Struktur data tree yang tidak memiliki
Baca selengkapnya