Selasa, 19 Mei 2020
Heaps
Pengenalan
Heap adalah sebuah struktur data berbasis tree yang memenuhi kondisi heap. Berikut merupakan kondisi-kondisi heap:
- Min Heap: Setiap node lebih kecil dari anaknya
- Max Heap: Setiap node lebih besar dari anaknya
Dari kondisi itu, kita dapat simpulkan bahwa node terkecil ada pada root (root dimulai dari index 1 u/ mempermudah dalam membuat relasi antar node), sementara node terbesar ada pada leaf. Heap bisa diimplementasikan dengan ArrayList, namun akan jauh lebih mudah jika menggunakan array.
Pengaplikasian heap pada priority queue:
- Selection Algorithm (mencari min/max, median, elemen terbesar, dll)
- Algoritma Dijkstra (mencari jalan terpendek dalam grafik)
- Algoritma Prim (mencari spanning tree yang minimum)
Sort pada heap memiliki efisiensi O(n.log(n)).
Dalam pengaplikasian heap pada priority queue, terdapat beberapa operasi seperti:
- find-min: mencari elemen terkecil dalam heap
- insert: memasukkan elemen baru dalam heap
- delete-min: menghapus elemen terkecil dalam heap
Relasi antar node pada heap dengan implemetasi array dapat dibuat dengan mudah, seperti berikut:
*misalkan index dari suatu node adalah n
- Index parent = x / 2
- Index left-child = x * 2
- Index right-child = (x * 2) + 1
Operasi
Find-min
Find-min dalam heap dapat dilakukan dengan mudah, karena node terkecil sudah pasti berada di root. Fungsi nya dapat dituliskan seperti:
int findMin(){
return data[1];
}
Insert
Min-Heap
Child dari node selalu lebih kecil dari pada parent.
Berikut adalah step by step dalam melakukan insert pada min-heap:
- Masukkan elemen baru ke bagian akhir heap (pada leaf)
- Jika node baru tersebut lebih besar daripada parentnya, lakukan upheap
- Upheap: bandingkan node dengan parentnya. Jika node > parent, tukarkan posisi antara node dengan parent. Kemudian loop terus hingga parent > node
Berikut adalah step by step dalam melakukan delete pada min-heap:
- Dalam operasi delete pada min-heap, kita hanya harus menghapus node terkecil yaitu root
- Gantikan root dengan node paling akhir dalam heap
- Kurangkan jumlah elemen dalam heap
- Lakukan downheap pada root agar sesuai dengan peraturan heap
- Downheap: bandingkan node dengan kedua childnya (kiri-kanan). Jika node > child, tukarkan posisi
antara node dengan child terkecil. Kemudian loop terus hingga node < child atau node telah menjadi leaf
Max-heap
Child selalu lebih besar dari parent. Cara insertnya sama saja dengan min-heap, hanya saja dengan kondisi yang berkebalikan.
Min-Max Heap
Untuk min-max heap, perhatikan gambar berikut:
Dari contoh diatas kita bisa melihat bagaimana child bisa lebih kecil/besar dari parent tergantung posisi levelnya. Jika node lebih kecil dari parent pada level genap, maka node akan lebih besar dari parent pada level ganjil. Root selalu merupakan elemen terkecil, elemen terbesar sudah pasti merupakan salah satu dari root child.
Insert pada min-max heap sama saja dengan min-heap atau max-heap, namun upheap nya sedikit berbeda. Berikut penjelasan terhadap upheap untuk min-max heap:
- Upheapmin: bandingkan nilai dari node dengan nilai dari grand parentnya. Jika nilai node lebih kecil dari parentnya, tukar nilai antara node dengan parent. Lalu, lanjutkan dengan upheapmin grand parentnya.
- Upheapmax: bandingkan nilai dari node dengan nilai dari grand parentnya. Jika nilai node lebih besar dari parentnya, tukar nilai antara node dengan parent. Lalu, lanjutkan dengan upheapmin grand parentnya.
Delete
Min-Heap
Berikut adalah step by step dalam melakukan delete pada min-heap:
Downheap: bandingkan node dengan kedua childnya (kiri-kanan). Jika node > child, tukarkan posisi
antara node dengan child terkecil. Kemudian loop terus hingga node < child atau node telah menjadi leaf- Dalam operasi delete pada min-heap, kita hanya harus menghapus node terkecil yaitu root
- Gantikan root dengan node paling akhir dalam heap
- Kurangkan jumlah elemen dalam heap
- Lakukan downheap pada root agar sesuai dengan peraturan heap
- Downheap: bandingkan node dengan kedua childnya (kiri-kanan). Jika node > child, tukarkan posisi antara node dengan child terkecil. Kemudian loop terus hingga node < child atau node telah menjadi leaf
Max-heap
Child selalu lebih besar dari parent. Cara deletionnya sama
saja dengan min-heap, hanya saja dengan kondisi yang berkebalikan.
Min-Max Heap
Untuk deletionnya, kita bisa menghapus node terkecil atau node terbesar. Berikut step nya:
- Deletion untuk node terkecil:
- Gantikan root dengan elemen paling akhir dalam heap
- Kurangkan jumlah elemen dalam heap
- Downheapmin dari root
- Deletrion untuk node terbesar:
- Gantikan antara child terbesar (kiri / kanan) dengan elemen paling akhir dari heap
- Kurangkan jumlah elemen dalam heap
- Downheapmax dari node
Downheapmin / Downheapmax:
Misalkan n adalah elemen terkecil dari child atau grand-child dari suatu node
- Jika m adalah cucu dari node:
- Jika m < node: Tukar nilai mereka
- Jika m > node: Tukar nilai mereka dan lanjutkan downheapmin dari m
- Jika m adalah anak dari node:
- Jika m < node: Tukar nilai mereka
Pengenalan
Tries (prefix tree) adalah struktur data tree yang terurut dan digunakan untuk menyimpan array asosiatif (biasanya string). Kata "Trie" sendiri berasal dari kata retrieval, karena tries dapat suatu kata dalam kamus hanya dengan prefix dari kata tersebut.
Tries merupakan tree dimana setiap vertex mewakili satu kata atau awalan. Root dari tries mewakili character kosong.
Suatu vertex yang mempunyai k jarak dari root, mempunyai juga jarak asosiatif prefix k. Misalkan a dan b adalah 2 vertices dimana a adalah parent dari b, maka b pasti mempunyai asosiatif prefix dari a.
Contoh:
Gambar di atas merupakan contoh tries yang menyimpan kata ALGO, API, BOM, BOSAN, dan BOR.
Code Tries
Struktur Tries dapat ditulis sebagai berikut:
struct trie {
char chr;
int word;
struct trie* edge[128];
}*root = 0;
root = (struct trie*)malloc(sizeof(struct trie));
root->chr = ";
root->word = 0;
NB: chr adalah karakter(char) yang disimpan dalam node
word adalah 1 jika ada kata yang terbentuk pada node tersebut, 0 jika tidak.
char chr;
int word;
struct trie* edge[128];
}*root = 0;
root = (struct trie*)malloc(sizeof(struct trie));
root->chr = ";
root->word = 0;
NB: chr adalah karakter(char) yang disimpan dalam node
word adalah 1 jika ada kata yang terbentuk pada node tersebut, 0 jika tidak.
Fungsi insert dapat ditulis sebagai berikut:
//fungsi insert
void insert(struct trie *curr, char *p) {
if(curr->edge[*p] == 0)
curr->edge[*p] = newNode(*p);
if(*p == 0)
curr->word = 1;
else
insert(curr->edge[*p], p+1);
}
//fungsi new node
struct trie* newNode(char x) {
struct trie* node = (struct trie*)malloc(sizeof(struct trie));
node->chr = x;
node->word = 0;
for(int i = 0; i < 128; i++)
void insert(struct trie *curr, char *p) {
if(curr->edge[*p] == 0)
curr->edge[*p] = newNode(*p);
if(*p == 0)
curr->word = 1;
else
insert(curr->edge[*p], p+1);
}
//fungsi new node
struct trie* newNode(char x) {
struct trie* node = (struct trie*)malloc(sizeof(struct trie));
node->chr = x;
node->word = 0;
for(int i = 0; i < 128; i++)
node->edge[i] = 0;
return node;
}
//fungsi main
char s[100];
insert(root, s);
}
//fungsi main
char s[100];
insert(root, s);
Fungsi find dapat ditulis sebagai berikut:
//fungsi find
void find(struct trie *curr, int x) {
if(curr->word == 1) {
s[x] = 0;
puts(s);
}
for(int i = 0; i < 128; i++) {
if(curr->edge[i] != 0) {
s[x] = i;
find(curr->edge[i], x+1);
}
}
}
void find(struct trie *curr, int x) {
if(curr->word == 1) {
s[x] = 0;
puts(s);
}
for(int i = 0; i < 128; i++) {
if(curr->edge[i] != 0) {
s[x] = i;
find(curr->edge[i], x+1);
}
}
}
//global variable
char s[100] = {""};
//fungsi main
int i, n, okay;
struct trie *curr;
n = strlen(s);
okay = 1;
curr = root;
for(i = 0; i < n && okay == 1; i++) {
if(curr->edge[s[i]] == 0)
okay = 0;
else curr = curr->edge[s[i]];
}
if(okay) find(curr, n);
char s[100] = {""};
//fungsi main
int i, n, okay;
struct trie *curr;
n = strlen(s);
okay = 1;
curr = root;
for(i = 0; i < n && okay == 1; i++) {
if(curr->edge[s[i]] == 0)
okay = 0;
else curr = curr->edge[s[i]];
}
if(okay) find(curr, n);
