Heap & Tries Martin Leonardo Hermawan 2301873043

Heap

Heap adalah struktur data berbasis tree dimana tree itu adalah complete binary tree. Secara umum, ada 2 jenis heap yaitu:

1. Max Heap : kunci yang ada di simpul akar harus paling besar diantara kunci yang ada d semua anak-anak itu. Properti yang sama harus benar secara rekursif untuk semua subtree di binary tree tersebut.
   
2. Min Heap : kunci yang ada di simpul akar harus minimum diantara kunci yang ada di semua anak-anak itu. Properti yang sama harus benar secara rekursif untuk semua subtree di binary tree tersebut.
   

Selain 2 heap diatas ada juga max-min heap yaitu complete binary tree yang berisi level min (atau genap) dan maks (atau ganjul) secara bergantian. Level genap dilambangkan seperti 0, 2, 4, dll, dan level ganjil dilambangkan dengan 1, 3, 5, dll. Berikut ini contohnya

Insertion

Pertama, meningkatkan ukuran heap oleh 1, sehingga dapat menyimpan elemen baru. Masukkan elemen baru di akhir heap. Elemen yang baru diinsert ini dapat merusak heap. Jadi, untuk menjaga heap, dilakukan heapify elemen yang baru diinsert dengan cara bottom-up.

Illustration:

Suppose the Heap is a Max-Heap as:
      10
    /    \
   5      3
  / \
 2   4

The new element to be inserted is 15.

Process:
Step 1: Insert the new element at the end.
      10
    /    \
   5      3
  / \    /
 2   4  15

Step 2: Heapify the new element following bottom-up 
        approach.
-> 15 is more than its parent 3, swap them.
       10
    /    \
   5      15
  / \    /
 2   4  3

-> 15 is again more than its parent 10, swap them.
       15
    /    \
   5      10
  / \    /
 2   4  3

Therefore, the final heap after insertion is:
       15
    /    \
   5      10
  / \    /
 2   4  3

Deletion

Ganti root atau elemen yang akan dihapus oleh elemen terakhir. Hapus elemen terakhir dari heap. Karena, elemen terakhir sekarang ditempatkan pada posisi node root. Jadi, mungkin tidak mengikuti properti heap. Oleh karena itu, heapify simpul terakhir yang ditempatkan di posisi root.

Illustration:

Suppose the Heap is a Max-Heap as:
      10
    /    \
   5      3
  / \
 2   4

The element to be deleted is root, i.e. 10.

Process:
The last element is 4.

Step 1: Replace the last element with root, and delete it.
      4
    /    \
   5      3
  / 
 2   

Step 2: Heapify root.
Final Heap:
      5
    /    \
   4      3
  / 
 2   

Tries

Trie adalah struktur data pencarian yang efisien. Kompleksitas pencarian dapat dilakukan dengan bata optimal (panjang key). Jika kita menyimpan kunci dalam binary search tree, binary seach tree yang seimbang akan membutuhkan waktu yang sama dengan  M * log N, dimana M adalah panjang string maksimum dan N adalah jumlah key dalam tree. Dengan menggunakan trie, kita dapat mencari key dalam waktu O(M). Namun, ada persyaratan penyimpanan trie. Setiap simpul trie terdiri dari banyak cabang. Setiap cabang mewakili karakter key yang memungkinkan. Kita perlu menandai simpul terakhir dari setiap key sebagai simpul kata terakhir. Bidang simpul isEndOfWord digunakan untuk membedakan simpul tersebut sebagai simpul akhir kata.