HEAP
Pengertian Heap Adalah struktur data yang berbentuk pohon yang memenuhi sifat-sifat heap yaitu jika B adalah anak dari A, maka nilai yang tersimpan di simpul A lebih besar atau sama dengan nilai yang tersimpan di simpul B.
Heap adalah complete binary tree (bukan binary search tree) yang mempunyai properties sebagai berikut:
- Min Heap
- Setiap node lebih kecil dari masing-masing childnya
- Root merupakan node paling kecil, sedangkan node terbesar terletak pada leaf node
- Max Heap
- Setiap node lebih besar dari masing-masing childnya
- Root merupakan node paling besar, sedangkan node terkecil terletak pada leaf node
- Min-Max Heap
- Heap dengan Min heap pada level ganjil dan Max heap pada level genap
Jenis-jenis Heap
1. Binary heap
adalah heap yang dibuat dengan menggunakan pohon biner.
2. Binomial heap
adalah heap yang dibuat dengan menggunakan pohon binomial.
Pohon binomial bila didefinisikan secara rekursif adalah:
• Sebuah pohon binomial dengan tinggi 0 adalah simpul tunggal
• Sebuah pohon binomial dengan tinggi k mempunyai sebuah simpul akar yang anak-anaknya adalah akar-akar pohon pohon binomial.
3. Fibonacci Heap
Fibonacci heap adalah kumpulan pohon yang membentuk minimum heap.
Pohon dalam struktur data ini tidak memiliki bentuk yang tertentu dan pada kasus yang ekstrim heap ini memiliki semua elemen dalam pohon yang berbeda atau sebuah pohon tunggal dengan tinggi Keunggulan dari Fibonacci heap adalah ketika menggabungkan heap cukup dengan menggabungkan dua list pohon.
TRIES
Tries atau prefix tree adalah suatu pohon struktur data yang terurut yang menyimpan data array, biasanya string. Kata tries diambil dari kata RETRIEVAL, karena tries dapat menemukan kata tunggal dalam kamus dengan hanya awalan katanya saja.
Tries sudah diterapkan ke banyak hal dalam kehidupan sehari-hari, contohnya pada web browser. suatu web browser dapat mengira atau mensugestikan kata-kata yang mungkin kita maksud saat kita mengetik huruf pertamanya saja. (autocomplete)
Contoh tries :
Pada gambar diatas menunjukan kata : ALGO, API, BOM, BOSAN, BOR.
