Rangkuman Pertemuan 11

Heap

Heap adalah struktur data berbentuk binary tree yang menggunakan array sebagai media pengimplementasiannya. Walaupun mirip dengan Binary Search Tree, Heap memiliki perbedaan yaitu antara anak kanan dengan anak kiri tidak memiliki hubungan. Jadi, yang menjadi patokan adalah parent dari node itu sendiri.

Min-Heap

Min-Heap adalah heap dengan urutan data dari yang paling kecil (root) sampai ke data yang paling besar.

Contoh Min-Heap

Max-Heap

Max-Heap adalah kebalikan dari Min-Heap, yaitu urutan datanya dari yang paling besar sebagai root, sampai ke data yang paling kecil.

Contoh Max-Heap

Min-Max Heap

Min-Max Heap adalah gabungan antara Min-Heap dengan Max-Heap dalam satu Heap. Jadi, level 0 dimulai dari min, dilanjutkan level 1 dengan max, level 2 dengan min, dan seterusnya.

Contoh Min-Max Heap

Heap : Insertion

1. Insert pada heap selalu dimulai dari index 1 dan seterusnya. 
2. Kemudian node yang baru di insert, akan dibandingkan dengan parentnya apakah lebih kecil / lebih besar (sesuai dengan heap, min / max). 
3. Apabila ternyata node yang baru di insert memiliki value lebih kecil pada min heap / value yang lebih besar pada max heap, maka tukar posisi node baru dengan parentnya. 
4. Lakukan tahap kedua dan ketiga secara recursive sampai ke root.
5. Karena menggunakan array, maka kita memanipulasi indexnya. 
6. Index Parent = Index current node / 2
7. Index Left Child = Index Parent * 2
8. Index Right Child = (Index Parent * 2) + 1

Heap : Deletion

Konsep deletion pada heap, serupa dengan priority queue, yaitu pop dari data yang berada di urutan paling pertama terlebih dahulu.

1. Swap data yang berada di index 1 dengan index terakhir.
2. Pop data yang berada di index terakhir.
3. Lakukan Heapify Down / pengecekan posisi node yang berada di index 1 (setelah swap) terhadap left child ataupun right child.
4. Apabila posisi nya ternyata salah, lakukan swap seperti pada insertion.
5. Ulangi tahap ke 3 dan ke 4 secara recursive, sampai tidak ada child lagi.

Contoh Codingan Min-Heap

#include<stdio.h>

int heap[101];

int idx = 1;

void swap(int a, int b){

int temp = heap[a];

heap[a] = heap[b];

heap[b] = temp;

}

void insert(int val){

heap[idx] = val;

int curr = idx;

while(curr/2 > 0 && heap[curr] < heap[curr/2]){

swap(curr,curr/2);

curr/=2;

}

++idx;

}

int extract(){

int result = heap[1];

heap[1] = heap[idx-1];

int curr = 1;

--idx;

while(curr*2 < idx && (heap[curr*2]<heap[curr] || heap[curr*2+1]<heap[curr])){

if(curr*2+1<idx){

if(heap[curr*2] < heap[curr*2 + 1]){

swap(curr,curr*2);

curr*=2;

}else{

swap(curr,curr*2+1);

curr = curr*2+1;

}

}else{

swap(curr,curr*2);

curr*=2;

}

}

return result;

}

void print(){

for(size_t i = 1; i < idx; ++i){

printf("%d ", heap[i]);

if(i==idx-1)printf(" \b");

y}

int main (){

insert(2);

insert(1);

insert(5);

insert(15);

insert(11);

insert(10);

print();

extract();

puts("");

print();

return 0;

}

Tries

Tries adalah struktur data yang berbentuk pohon, yang biasanya menyimpan data berupa string (kata). Kata tries diambil dari Retrieval, karena Tries dapat menemukan sebuah kata tunggal hanya dari huruf awalannya saja.

Contoh Tries

Demikian, rangkuman saya untuk pertemuan 11 kali ini. Semoga dapat membantu teman-teman sekalian. Terimakasih.