Heap and Tries

Heap adalah struktur data “complete binary tree based” yang memenuhi heap property. 
Property tersebut adalah:

•  Min Heap
•  Max Heap

      Min Heap

• Setiap elemen node lebih kecil dari elemen children-nya.
• Ini menyiratkan bahwa elemen terkecil terletak di root tree.
• Elemen terbesar terletak di suatu tempat di salah satu leaves node.
• Heap dapat diimplementasikan menggunakan linked-list, tetapi jauh lebih mudah untuk mengimplementasikan heap using array.

(Insertion)

(Delete part 1)

(Delete part 2)

      Max Heap

• Setiap elemen Node lebih besar dari elemen children-nya.
• Ini menyiratkan bahwa elemen terbesar terletak di root tree.
• Max heap memiliki prinsip yang sama dengan min heap.

     Min-Max Heap

•  Kondisi heap bergantian setiap level, setiap level berselang-seling antara minimum dan maksimum.

·         Setiap elemen pada level genap / ganjil lebih kecil dari semua children-nya (level min).

·         Setiap elemen pada level ganjil / genap lebih besar dari semua children-nya(level max).

• Tujuan heap min-max adalah untuk menemukan elemen heap terkecil dan terbesar sekaligus.

(Contoh min max heap)

(Insertion)

(Delete part 1)

(Delete part 2)

(Delete part 3)

(Delete part 4)

Tries

• Tries adalah tree dimana setiap node mewakili satu kata atau awalan.
• Root adalah karakter kosong. 
• Biasa digunakan untuk auto complete text, spell checker, dll.

(Contoh tries)

Source: PPT Heaps and Tries session 11