HEAP & TRIES

Hallo semua, kembali lagi dengan materi Data Struct. Kali ini, gue bakalan bahas tentang heap and tries.

Q: LAH AGA MUNCUL LU TBTB BAWA MATERI YG GA PERNAH W DENGER. APAAN TUH!!??
A: YA MAAP NAMANYA TUGAS MANA GUE TAU LU PERNAH DENGER APA ENGGA.
Q: LOH KOK NGE GAS?
A: LAH? YA MAAP
Q: YAUDAH LANJUT DAH MATERI LU BIAR GUE DENGERIN
A: OK SIMAK YE.

HEAP

Nah, jadi guys Heap adalah complete binary tree (bukan binary search tree) yang mempunyai properties sebagai berikut:

Min Heap terdiri atas Setiap node(parents) lebih kecil dari masing-masing childnya
Root merupakan node paling kecil, sedangkan node terbesar terletak pada leaf node

min heap

Max Heap terdiri atas Setiap node(parents) lebih besar dari masing-masing childnya
Root merupakan node paling besar, sedangkan node terkecil terletak pada leaf node

max heap

Setelah itu ada juga min-max heap.

Min-max heap adalah Heap dengan Min heap pada level ganjil(1,3,5 dst) dan Max heap pada level genap(2,4,6,8,dst)

min max heap

Heap bisa diimplementasi dengan array maupun dengan linked list. Aplikasi heap merupakan menjadi berikut:

Priority Queue

1. Selection algorithm
2. Dijkstra's Algorithm
3. Prim Algorithm

Implementasi heap memakai array yaitu Array dimulai menggunakan indeks ke 1
Rumus umum pelaksanaan heap dengan array (x adalah current node):

• Parent(x): x/2
• Left-child(x): 2*x
• Right-Child(x): 2*x+1

Operasi pada Min Heap

• Find-Min

Minimum node terletak pada root

• Insertion pada Min-heap

Insert node selalu berurutan berdasarkan level paling rendah menggunakan urutan left ke right

New node selalu menjadi leaf node

Sesuikan sesuai heap properties secara rekursif

• Deletion-Min dalam Min-Heap

Node yg dihapus selalu root karena merupakan node paling kecil, kemudian diganti dengan node yang paling terakhir di insert

Sesuaikan dengan heap properties secara rekursif

Operasi pada Max Heap

Insertion dan deletion untuk Max heap, hanya saja disesuakan menggunakan properties Max-Heap

• Min-Max Heap

Insert node sinkron urutan, lalu cek upheap lalu sesuaikan dengan properties level.

Umumnya dilakukan penyesuaian rekursif dengan urutan menjadi berikut:

1. Parent
2. Grand Parent

• Deletion selalu dilakukan dalam root, kemudian sesuaikan menggunakan downheap sesuai properties

Umumnya dilakukan penyesuaian secara rekursif dengan urutan sebahai berikut:

1. Grand child
2. Child ( grand child disesuaikan menggunakan parentnya)

TRIES

Trie adalah struktur data pencarian informasi yang efisien.

 Menggunakan Trie, kompleksitas pencarian dapat dibawa ke batas optimal (panjang kunci). Jika kita menyimpan kunci dalam BST, BST yang seimbang akan membutuhkan waktu yang proporsional dengan M * log N, di mana M adalah panjang string maksimum dan N adalah jumlah kunci dalam pohon. Dengan menggunakan Trie, kita dapat mencari kunci dalam waktu O (M).

tries

Jadi kesimpulannya Tries adalah tree yang dilakukan buat menyimpan array asosiatif

Properties pada tries terdiri atas:

1. Setiap vertex/node merepresentasikan satu huruf
2. Root merepresentasikan karakter kosong
3. Aplikasi pada trees adalah fitur auto-complete yg ada pada web-browser

SEKIAN DAN TERIMA KASIH

credit:
https://www.geeksforgeeks.org/binary-heap/
https://en.wikipedia.org/wiki/Min-max_heap
https://www.geeksforgeeks.org/minimum-element-in-a-max-heap/
https://www.geeksforgeeks.org/max-heap-in-java/
https://www.geeksforgeeks.org/trie-insert-and-search/