Heap & Tries

Max-Min heap

dalam max-min heap, max dan min bergantian pada setiap level

level ganjil memakai max heap

level genap memakai min heap

FFind-Min in Min-Heappertama kita harus tahu dulu apa itu heap

Heap sendiri merupakan complete binary tree berdasarkan struktur data yang memenuhi properti heap.

nah properti apa yang dimiliki heap

- Min Heap

setiap element node lebih kecil dari childrennya.

- Max Heap

setiap element node lebih besar dari childrennya.

pertama kita bahas dulu min heap

seperti yang dijelaskan tadi Min heap setiap element nodenya lebih kecil dari childrennya artinya elemen terbesar terletak di suatu tempat di salah satu leaf node. Heap dapat diimplementasikan menggunakan linked-list, tetapi jauh lebih mudah untuk mengimplementasikan heap dengan array.

berikut contoh dari Min Heap

lalu heap memiliki beberapa aplikasi

1. Priority Queue

- Algoritma Pilihan (menemukan elemen min / maks, median, elemen kth- terbesar, dll).

- Algoritma Dijkstra (menemukan jalur terpendek dalam grafik).

- Algoritma Prim (menemukan pohon rentang minimum).

2. Heap Sort

- An O(n.lg(n)) algorithm.

MIN HEAP

PRIORITY QUEUE

Heap adalah implementasi efisien dari priority queue data structure.

- find-min: cari elemen terkecil di heap.

- insert: memasukkan elemen baru ke heap.

- delete-min: hapus elemen terkecil dari heap.

untuk delete-min dan insert sama halnya namanya seperti pop dan push.

ARRAY IMPLEMENTATION

heap biasanya mengimplementasikan dalam bentuk array.

Elemen-elemen disimpan secara berurutan dari indeks 1 ke N dari atas ke bawah dan dari node kiri ke kanan tree.

Root disimpan dalam indeks 1

(kami membiarkan indeks 0 kosong / tidak digunakan, untuk tujuan kenyamanan).

Cara menghitung index bisa seperti ini

anggap current node adalah sebuah index x maka

parent(x) = x/2

left-child(x) = 2*x

right-child(x) = 2*x+1

Inilah mengapa kita menggunakan indeks 1 sebagai root, jika tidak

hubungan tidak akan muncul.

Find-Min in Min-Heap

untuk mencari nilai minimum dalam min heap bisa dilakukan dengan

int findmin() {return data[1];}

INSERTION IN MIN-HEAP

insert untuk min-heap ada 2 cara yaitu

1. Upheap

Masukkan node seperti biasa, lalu bandingkan dengan node di atasnya (parent) bila parent nilai nya lebih besar, tukar. Setelah ditukar lakukan hal yang sama dengan node diatasnya. Berhenti ketika node yang diatas nya sudah lebih kecil.

2. Downheap

Masukkan node seperti biasa, mulai dari node root, bandingkan dengan left dan right child, bila lebih kecil, tukar node nya dengan node yang lebih kecil. lanjutkan terus dan berhenti bila node dibawahnya.

Heap Complexity

find-min: O (1)

insert: O (log (n))

delete-min: O (log (n))

insert dan delete-min tergantung pada ketinggian tree, yang

adalah log (n), ketinggian binary tree lengkap.

MAX HEAP

Setiap elemen node lebih besar dari elemen childnya.

Ini menyiratkan bahwa elemen terbesar terletak di root pohon.

Max-heap memiliki prinsip yang sama dengan min-heap dan dapat digunakan untuk membuat queue priority yang perlu menemukan elemen terbesar alih-alih yang terkecil.

MIN-MAX HEAP

dalam max-min heap, max dan min bergantian pada setiap level

Setiap elemen pada level genap / ganjil lebih kecil dari semua childnya (level min).

Setiap elemen pada level ganjil / genap lebih besar dari semua childnya (level maksimal).

INSERTION PADA MIN-MAX HEAP

masukkan node seperti biasa,

bila node ada di min heap:

- jika node parent lebih kecil, tukar node sekarang dengan node parent, lalu cek grand parent dari nodenya, bila lebih kecil, tukar.

bila node ada di max heap:

- jika node parent lebih besar, tukar node sekarang dengan node parent, lalu cek grand parent dari nodenya, bila lebih besar, tukar.

DELETION PADA MIN-MAX HEAP

Penghapusan elemen terkecil

- Ganti root dengan elemen terakhir di heap.

- Kurangi jumlah elemen dalam tumpukan.

- Downheapmin dari root.

Penghapusan elemen terbesar

- Ganti child kiri atau child kanan root (tergantung mana yang lebih besar) dengan elemen terakhir di heap.

- Kurangi jumlah elemen dalam tumpukan.

- Downheapmax dari node.

TRIES

Tries (prefix tree) adalah 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.

Nama : Antonio Michael Kurniawan

NIM : 2301924063