Laporan Materi Pembelajaran Data Structure : Heap & Tries

Di post yang satu ini, saya akan membahas materi Data Structure yang membahas tentang Heap dan Tries, selamat membaca!
Heap

Heap adalah data structure berbasis binary tree yang diimplementasikan menggunakan array, yang mana array adalah kumpulan elemen yang disimpan di lokasi memori yang berdekatan dengan ide untuk menyimpan beberapa item dari jenis yang sama bersamaan.

Ada beberapa jenis dari heap, yakni:

  • Min-heap
Nilai setiap node lebih besar dari atau sama dengan nilai induknya, dengan nilai minimum pada node akar.
Contoh dari min-heap












  • Max-heap

Nilai setiap node kurang dari atau sama dengan nilai induknya, dengan nilai maksimum pada node akar.
Contoh dari max-heap












Terdapat syarat-syarat struktural dari heap, yaitu:
  • Semua level heap harus penuh, kecuali yang terakhir
  • Node harus diisi dari kiri ke kanan.
  • Nilai-nilai di child kanan dan kiri atau node tidak berpengaruh apa-apa.

Terdapat juga operasi-operasi yang bisa dilakukan pada heap, yaitu:
  • Find -> mencari item pada heap
  • Insert -> menambahkan item di heap dan memastikan properti heap dipertahankan min-heap dan max-heap property
  • Delete -> menghapus item pada heap
  • Extract -> mengembalikan nilai suatu item lalu menghapusnya dari heap.
  • Replace -> extract atau pop root dan memasukkan atau mendorong item baru di heap dan memastikan properti heap telah mempertahankan min-heap dan max-heap property.
Dalam mengimplementasikan heap tentu akan ada keuntungan dan kerugiannya. Keuntungan dalam menggunakan heap yakni:
  • Dapat mengakses item terkecil dengan cepat. Heap memungkinkan kita untuk mengambil item terkecil (root) dalam O (1) O (1) waktu, sambil menjaga operasi lain relatif ringan.
  • Heap juga biasanya diimplementasikan dengan array, menghemat overhead dari menyimpan pointer ke node anak.
Sedangkan kerugian dalam penggunaan heap yaitu:
  • Heap hanya menyediakan akses mudah ke item terkecil. Menemukan item yang lainnya di heap membutuhkan O (n) O (n) waktu, karena kita harus beralih melalui semua node.

Tries

Tries adalah data structure tree terurut yang digunakan untuk menyimpan array asosiatif.

Ciri-ciri dari tries yakni:
  • Setiap vertex mewakili satu kata atau awalan.
  • Root mewakili karakter kosong (‘’).
  • Sebuah vertex yang merupakan tepi k jarak dari root memiliki awalan terkait panjang k.

Layaknya heap, tries juga mempunyai kelebihan dan kekurangan. Kelebihan dari penggunaan tries adalah:
  • Terkadang tries bisa menjadi pilihan yang hemat. Jika kita menyimpan banyak kata yang dimulai dengan pola yang sama, percobaan dapat mengurangi biaya penyimpanan keseluruhan dengan menyimpan awalan bersama satu kali.
  • Efisien pada query prefix. Tries dapat dengan cepat menjawab pertanyaan tentang kata-kata dengan awalan yang sama.
Sedangkan kekurangan dari tries yakni:
  • Tries lebih jarang menghemat ruang jika dibandingkan dengan menyimpan string dalam satu set.
  • Sebagian besar bahasa tidak dilengkapi dengan implementasi built-in trie sehingga harus menerapkannya sendiri.



Comments

Post a Comment