Heap

Heap adalah complete binary tree untuk mencari nilai terkecil atau terbesar dari suatu tree.

Ada 3 jenis Heap :

• Min-Heap
• Max-Heap
• Min-Max Heap

Min-Heap

• Setiap node memiliki nilai yang lebih kecil dari nilai anaknya.
• Elemen paling kecil terletak pada Root.
• Elemen paling besar terletak pada salah satu leaf.
• Dapat di implementasikan menggunakan linked list, tetapi lebih mudah menggunakan array.

Contoh Min-Heap

Operasi pada Min-Heap

• Insertion
  • Masukkan elemen baru pada ujung akhir heap.
  • Bandingkan nilai elemen yang dimasukkan dengan parent. Bila nilai node yang baru saja dimasukkan lebih kecil dari parent, Tukar node dengan parent. Lanjutkan proses ini ke atas sampai nilai parent lebih kecil dari nilai node atau node sudah mencapai root.
  • Contoh Insertion Min-Heap

• Deletion
  • Gantilah root dengan elemen terakhir pada heap.
  • Kurangi jumlah elemen pada heap.
  • Bandingkan nilai root dengan nilai left child dan right child. Bila ada nilai anaknya yang lebih kecil dari nilai root, Tukar root dengan anaknya (anak yang nilainya paling kecil). Lanjutkan proses ini ke bawah sampai nilai node lebih kecil dari nilai kedua anaknya atau node sudah mencapai leaf.
  • Contoh Deletion Min-Heap

Max-Heap

• Setiap node memiliki nilai yang lebih besar dari nilai anaknya.
• Elemen paling besar terletak pada Root
• Elemen paling kecil terletak pada salah satu leaf

Min-Max Heap

• Kondisi heap berganti antara minimum dan maximum antar level
• Setiap elemen pada level genap lebih kecil dari anak-anaknya.
• Setiap elemen pada level ganjil lebih besar dari anak-anaknya.
• Elemen paling kecil terletak pada Root.
• Elemen paling besar terletak pada salah satu anak Root.
• Contoh Min-Max Heap

Operasi pada Min-Max Heap

• Insertion
  • jika new node ada di Min level
    • jika parent dari new node lebih kecil, tukar posisi dan lakukan upheapmax dari parent.
    • jika kondisi diatas tidak benar, lakukan UpHeapMin.
    • UpHeapMin :
      • Bandingkan nilai node dengan grand-parent. Bila nilai node lebih kecil, Tukar nilai node dengan grand-parent dan Lanjutkan Upheapmin dari grand-parent.
  • jika new node ada di Max level
    • jika parent dari new node lebih besar, tukar posisi dan lakukan upheapmin dari parent.
    • jika kondisi diatas tidak benar, lakukan UpHeapMax.
    • UpHeapMax :
      • Bandingkan nilai node dengan grand-parent. Bila nilai node lebih besar, Tukar nilai node dengan grand-parent dan Lanjutkan Upheapmax dari grand-parent.
• Deletion
  • Deletion Elemen Terkecil
    • Gantilah root dengan elemen terakhir pada heap.
    • Kurangi jumlah elemen pada heap
    • DownHeapMin dari Root
    • DownHeapMin :
      • M adalah elemen terkecil dari antara anak-anak dan cucu-cucu dari node.
      • Bila M adalah cucu dari node :
        • Jika nilai M lebih kecil dari node, maka :
          • Tukar nilai M dengan node
          • Bila sesudah ditukar nilai m lebih besar dari parent-nya, Tukar nilai M dengan parent.
          • Lanjutkan DownHeapMin dari M
      • Bila M adalah anak dari node :
        • Jika nilai M lebih kecil dari node, Tukar nilai M dengan node.
  • Deletion Elemen Terbesar
    • Gantilah left child atau right child dari root (tergantung mana yang lebih besar) dengan elemen terakhir pada heap.
    • Kurangi jumlah elemen pada heap
    • DownHeapMax dari node tersebut.
    • DownHeapMax :
      • Prosesnya sama dengan Downheapmin, tetapi relational operator-nya dibalik.

Tries

Tries Adalah salah satu konsep struktur data yang digunakan untuk menyimpan string dalam array.

Contoh Tries :

Hashing

Hashing adalah mengubah sebuah string of characters menjadi suatu key yang merepresentasikan string aslinya.

Hashing digunakan untuk index dan mengambil item pada database.

Hash table adalah sebuah tabel dimana kita menyimpan original string. Index dari tabel adalah hashed key, sedangkan value yang disimpan adalah original string.