Heap and Tries

Heap and Tries

HEAP

Suatu heap tree adalah Complete Binary Tree (CBT) di mana harga-harga key pada node-nodenya sedemikian rupa sehingga haga-harga key pada node-node anaknya tidak ada yang lebih besar dari harga key pada node orang tuanya.

Heap tree memiliki properties seperti :

• Min Heap
• Setiap node lebih kecil dari masing-masing childnya
• Root merupakan node paling kecil, sedangkan node terbesar terletak pada leaf node

Sumber : http://gabrielyakub.blogspot.com/2016/05/pertemuan-8-heap-tries-hashing.html

• Max Heap
• Kebalikan dari Min-Heap, dimana root dari Max-Heap merupakan node dengan bilangan terbesar, dan nilai/bilangan children nya selalu lebih kecil dibandingkan parent nya (semakin kebawah semakin kecil)

Sumber : http://gabrielyakub.blogspot.com/2016/05/pertemuan-8-heap-tries-hashing.html

• Min-Max Heap
• adalah heap yang urutan Min dan Max nya selang seling
• Syarat Min-Max Heap:
• Min pada level 0 (root) selalu yang terkecil
• Max pada Level 1 selalu yang terbesar

Sumber : http://gabrielyakub.blogspot.com/2016/05/pertemuan-8-heap-tries-hashing.html

Implementasi Priority Queue

• heap tree bermanfaat untuk mengimplementasikan priority queue. Sebagai suatu priority queue, heap tree memerlukan beberapa metoda sebagai berikut:
• Metoda untuk menginisialisasi suatu CBT (Complete Binary Tree) a secara umum menjadi heap tree.
• Metoda untuk mengambil data paling besar, yaitu root dari heap tree. 
• Metoda untuk menambahkan satu key baru ke dalam heap tree. 
• Metoda untuk menyusun ulang menjadi heap tree kembali setelah dilakukan metoda b atau c 

Insertion Heap

• Saat sebuah data baru dimasukkan dalam heap, maka data langsung ditempatkan di index terakhir dalam heap. Setelah itu, data di-upheap. Maksudnya, data dibandingkan dengan parentnya. Bila lebih kecil, maka swap dengan parentnya. Hal ini dilakukan sampai data tersebut lebih besar dari parentnya.

Deletion Heap

• Jika dalam insertion dipakai Upheap, maka dalam deletion dipakai Downheap. Deletion dalam heap otomatis menghapus node root dari heap. Jadi, delete min dalam min heap dan delete max dalam max heap.
• Dalam deletion, node paling akhir langsung menggantikan root yang didelete. Kemudian, node tersebut langsung di downheap sampai ke posisinya.

TRIES

   

• Tries adalah tree yang dilakukan untuk menyimpan array asosiatif
• Properties pada tries:

1. Setiap vertex/node merepresentasikan satu huruf
2. Root merepresentasikan karakter kosong

• Aplikasi pada trees adalah fitur auto-complete yang ada pada web-browser

Sumber : https://brilliant.org/wiki/tries/