Heaps and Tries
HEAP Heap merupakan complete binary tree dan biasanya diimplementasikan dalam bentuk array, meskipun bisa juga diimplementasikan dalam bentuk linked list. Aplikasi Heap - Menemukan nilai terkecil/terbesar, median, dan lain-lain - Algoritma Dijkstra (Menemukan jalur terpendek dalam graf) - Algoritma Prim (Menemukan minimum spanning tree) Min Heap Setiap node memiliki nilai yang lebih kecil dibandingkan anaknya. Elemen terkecil berada pada root dan elemen terbesar berada pada node leaf. Fungsi pada Min Heap: find-min, insert, delete-min Implementasi Min Heap pada Array Biasakan index 1 dijadikan sebagai root. Jika current node adalah x, maka - Parent(x) = x/2 - Left-child(x) = 2*x - Right-child(x) = 2 * x + 1 Find-min = nilai pada root(index ke-1) karena nilai paling kecil berada pada root. Insert = Insert elemen baru di posisi akhir (index terakhir) pada heap, kemudian bandingkan node baru tersebut dengan parentnya. Jika current node lebih keci