Struktur Data Heap: Pengertian, Karakteristik, dan Operasinya

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

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