HEAP & TRIES

Heap

Heap adalah tree khusus berbentuk complete binary tree.  Ada 2 macam binary tree, yaitu:
1. Max-Heap: Dalam Max-Heap key yang ada di simpul akar harus paling besar di antara key yang ada di semua anak-anak. Properti yang sama harus benar secara rekursif untuk semua sub-pohon di Pohon Biner itu.

2. Min-Heap: Dalam Min-Heap key yang ada di simpul akar harus minimum di antara key yang ada di semua anak-anak itu. Properti yang sama harus benar secara rekursif untuk semua sub-pohon di Pohon Biner itu.

Cara Insert dalam Heap max/min:
1. Buat simpul baru di akhir heap.
2. Tetapkan nilai baru ke node.
3. Bandingkan nilai simpul anak ini dengan induknya.
4. Jika nilai orang tua kurang/lebih dari anak, maka tukarlah.
5. Ulangi langkah 3 & 4 sampai properti Heap bertahan.

Cara Delete dalam Heap max/min:
1. Hapus simpul root.
2. Pindahkan elemen terakhir dari level terakhir ke root.
3. Bandingkan nilai simpul anak ini dengan induknya.
4. Jika nilai orang tua kurang/lebih dari anak, maka tukarlah.
5. Ulangi langkah 3 & 4 sampai properti Heap bertahan.

Aplikasi Heap:
1.Priority Queue
   -Selection Algorithms
   -Dijkstra’s Algorithm
   -Prim Algorithm
2.Heap Sort

Trie

Trie adalah tree yang nodenya menyimpan kata atau string dan disusun di dalam node-node dengan cara tertentu. Sebuah node dalam trie berisi 2 hal, yaitu: value atau NULL dan array referensi ke node anak atau NULL. Waktu untuk mencari, menyisipkan, dan menghapus dari suatu trie tergantung pada panjang kata yang dicari, dimasukkan, atau dihapus, dan jumlah total kata, n, membuat runtime dari operasi ini adalah O(n). Keuntungan dari trie ini adalah dapat dengan mudah mencetak semua kata dalam urutan abjad dan lebih cepat dari BST maupun hashing. Selain itu, dapat melakukan pencarian awalan kata seperti di search  engine.

Aplikasi trie:
1.Search Engines
2.Genome Analysis
3.Data Analytics