Heaps & Tries

Heaps & Tries 

Heap
Heap adalah struktur data berbasis pohon biner lengkap yang memenuhi properti heap. Heap biasanya diimplementasikan dalam sebuah array. Elemen disimpan secara berurutan dari indeks 1 ke N dari atas ke bawah dan dari node kiri ke kanan pohon. Root disimpan dalam indeks adalah 1

Apa jenis-jenis Heap properti?

• Min Heap: Setiap elemen node lebih kecil dari elemen anak-anaknya. Ini menyiratkan bahwa elemen terkecil terletak di akar pohon. Elemen terbesar terletak di suatu tempat di salah satu node daun. Heap dapat diimplementasikan menggunakan linked-list, tetapi jauh lebih mudah untuk mengimplementasikan heap menggunakan array.

Contoh Min Heap:

Aplikasi Heap

Antrian Prioritas

• Algoritma Seleksi (menemukan elemen min / maks, median, elemen kth-terbesar, dll). 
• Algoritma Dijkstra (menemukan jalur terpendek dalam grafik). 
• Algoritma Prim (menemukan pohon rentang minimum).

Implementasi Antrian Prioritas terdiri dari:

• Find-min: Mencari elemen terkecil di heap. int findmin(){return data[1];} 
• Insert (Push): Masukkan elemen baru ke dalam tumpukan. 
• Delete-min (Pop): Menghapus elemen terkecil dari heap.

Insert in Min-Heap

Agar saat melakukan insert element baru, dan tetap menjaga property heap, dilakukan Upheap (memperbaiki property heap tersebut). Uphead adalah membandingkan nilai node saat ini (mulai dengan node yang disisipkan) dengan nilai induknya. Jika nilai node saat ini lebih kecil dari nilai induknya daripada menukar nilainya dan teruskan upheap node induknya. Berhenti jika nilai induknya lebih kecil dari nilai node  saat ini atau node saat ini adalah root (tidak memiliki induk).

Contoh insert:

Insert node (20)

< Insert node (5) >

Deletion in Min-Heap

Penghapusan elemen terkecil yang terletak di root. Root diganti dengan elemen terakhir dari heap. kemudian kurangi jumlah elemen dalam heap. dan gunakan root Downheap (memperbaiki properti heapnya).

Downheap adalah membandingkan nilai node saat ini (mulai dengan root) dengan nilai anak kiri dan kanannya. Tukar node saat ini dengan anak terkecil dan lanjutkan downheaps pada node (anak) itu. Berhenti jika nilai node saat ini lebih kecil dari nilai anak-anaknya atau node saat ini adalah leaf (tidak memiliki anak).

Contoh Deletion:

Delete-min, node (7)

Penggatian root dengna element terakhir, node (28).

• Max Heap: Setiap elemen node lebih besar dari anak-anaknya.Ini menyiratkan bahwa elemen terbesar terletak di akar pohon. Max-heap memiliki prinsip yang sama dengan min-heap dan dapat digunakan untuk membuat antrian prioritas yang perlu menemukan elemen terbesar alih-alih yang terkecil.

Min Max Heap

Konsep Min Max Heap adalah level root akan bernilai minimum, selanjutnya akan bernilai maximum, dan seterusnya. Nilai terkecil berada di root dan nilai terbesar berada di salah satu node pada level setelah root. Level min hanya dapat dibandingkan dengan level min, dan sebaliknya. Insertion dan Deletion sama seperti Min Heap atau Max Heap namun, pengecekan kondisi hanya dapat dilakukan di level sesama min atau max.

Contoh:

Tries

Tries (prefix tree) adalah pohon di mana setiap simpul mewakili satu kata atau awalan. Struktur data tree terurut yang digunakan untuk menyimpan array asosiatif (biasanya string) Istilah TRIE berasal dari kata RETRIEVAL karena mencoba dapat menemukan satu kata dalam kamus dengan hanya awalan kata.