HEAP AND TRIES

Heap adalag binary tree lengkap yang berdasarkan struktur data dimana value key pada node nya diatur sedemikian rupa sehungga value key pada node anaknha tidak ada yang lebih besar dari value key node orang tuanya.

Terdapat 2 macam heap :

•    Min Heap

Setiap elemen node lebih kecil dari anaknya

•    Max Heap

Setiap elemen node lebih besar dari anaknya

MIN HEAP

Setiap elemen node lebih kecil dari elemen anaknya. Element heap terbesar terleta di salah satu leaf node. Heap bisa diimplementasikan dengan linked-list, tetapi lebih mudah diimplementasikan dengan array.

Contoh Min-Heap

Aplikasi penggunaan Heap

•    Priority Queue

•    Selection Algorithm

•    Dijkstra’s Algortihm

•    Prim Algorithm

•    Heap Sort

Insertion di Min-Heap

Menginput element baru di akhir heap. Membandingkan nilai node sekarang dengan nilai parent nya. Jika nilai node sekarang lebih kecil dari parent nya, tukar nilainya. Berhenti menukar jika nilai parent nya lebih kecil dari nilai node sekarang.

Contoh insertion Min-Heap

Deletion di Min-Heap

Menukar root dengan element terakhir heap. Mengurangi jumlah element di dalam heap. Membandingkan nilai node sekarang dengan nilai di kiri dan kanan. Menukar nilai node sekarang dengan child terkceil. Berhenti menukar jika nilai node yang sekarang lebih kecil daripada nilai children nya.

Contoh Deletion Min-Heap

MAX-HEAP

Setiap elemen node lebih besar dari element children nya. Ini menyatakan jika elemen terbesar terletak di root.

MIN-MAX HEAP

Kegunaan dari  min-max untuk mencari elemen terbesar dan terkecil dari heap dalam waktu yang bersamaan.

Contoh MIN-MAX HEAP

Dalam Min-Max Heap elemen terkecil terdapat di root. Elemen terbesar terletak di salah satu root’s child.

Insertion di Min-Max Heap

Insert elemen baru di akhir heap. Upheap elemen baru. 

 Deletion di Min-Max Heap

Deletion elemen terkecil

·        Menukar root dengan elemen terakhir di heap

·        Mengurangi jumlah elemen heap

·        Dowheapamin dari root

Deletion elemen terbesar

·        Menukar left-child atau right-child dari root

·        Mengurangi jumlah elemen di heap

·        Downheapmax dari node

Contoh deletion Min-Max Heap

TRIES

Tries adalah struktur data tree berurutan yang digunakan untuk menyimpan array yang asiosiatif.

Aplikasi penggunaan tries

·        Penyelesaian otomatis tulisan yang akan dicari pada browser

·        Pemeriksa ejaan

Contoh dari tries

 reference :

http://www.algolist.net/Data_structures/Binary_heap/Insertion

https://www.tutorialspoint.com/data_structures_algorithms/heap_data_structure.htm

http://www.mathcs.emory.edu/~cheung/Courses/171/Syllabus/9-BinTree/heap-delete.html

https://medium.com/@randerson112358/max-heap-deletion-step-by-step-f402861523dahttp://people.cs.ksu.edu/~rhowell/DataStructures/trees/tries/intro.html