Heap
Heap adalah sebuah data struktur yang bisa direpresentasikan sebagai binary tree. Walaupun digambarkan sebagai sebuah binary tree, kita bisa mengimplementasikannya dengan array juga karena cara kerja heap.
Heap mempunyai banyak manfaat di dunia informatika, salah satu implementasinya adalah heap sort, tetapi yang paling sering digunakan adalah implementasi heap sebagai priority queue.
Berikut adalah contoh heap:
Ada 3 jenis heap yang akan kita pelajari hari ini, yaitu:
1. Min Heap.
2. Max Heap.
3. Min-Max Heap.
1. Min heap
Min heap adalah jenis heap yang sesuai dengan namanya mengutamakan nilai paling kecil. Ini artinya root node adalah angka terkecil di dalam heap tersebut dan semua child dari node akan selalu lebih besar daripada parent-nya.
Contoh Min Heap:
Insertion node dalam min heap selalu mulai dari tangan kiri terlebih dahulu, jadi berbeda dari insertion pada BST. Setelah menginsert value, kita harus mengcompare data dahulu apakah data tersebut lebih besar dari data yang diinsert. Jika data lebih besar, kita akan melakukan swap dan menukar nilai. Proses ini berlanjut hingga kita mengcompare dengan root node.
Deletion node dalam min heap akan selalu menghapus root node atau node dengan nilai terkecil. Setelah kita hapus kita akan mengcompare dengan tangan kiri dan tangan kanan dan mencari node terkecil yang baru agar nantinya kita swap dengan root node. Setelah itu jika ada nilai yang tidak memenuhi syarat min-heap, kita akan melakukan perjalanan kebawah lagi dan operasi swap lagi.
Berikut adalah contoh code insertion dan deletion pada Min Heap:
Code :
#include <stdio.h>
const int s = 20;
int idx = 1;
void swap(int &a, int &b){
int temp = a;
a = b;
b = temp;
}
void insert(int arr[], int val){
int parent = idx/2;
int curr = idx;
if(arr[idx] == -1){
arr[idx] = val;
}
while(arr[curr] < arr[parent] && curr != 1){
swap(arr[curr], arr[parent]);
curr = parent;
parent = curr/2;
}
idx++;
}
void del(int arr[], int val){
swap(arr[1], arr[idx-1]);
arr[idx-1] = -1;
idx--;
int leftChild = 1 * 2;
int rightChild = 1 * 2 + 1;
int curr = 1;
while(arr[leftChild] < arr[curr] || arr[rightChild] < arr[curr] && (arr[leftChild] != -1 && arr[rightChild] != -1) ){
if(arr[leftChild] < arr[rightChild] && (arr[leftChild] != -1 && arr[rightChild] != -1) ){
swap(arr[curr], arr[leftChild]);
curr = leftChild;
leftChild = curr * 2;
rightChild = curr * 2 + 1;
}
else if(arr[rightChild] < arr[leftChild] && (arr[leftChild] != -1 && arr[rightChild] != -1) ){
swap(arr[curr], arr[rightChild]);
curr = rightChild;
leftChild = curr * 2;
rightChild = curr * 2 + 1;
}
else{
if(arr[leftChild] == -1 && arr[rightChild] == -1){
break;
}
else if(arr[leftChild] == -1){
swap(arr[curr], arr[rightChild]);
curr = rightChild;
leftChild = curr * 2;
rightChild = curr * 2 + 1;
}
else{
swap(arr[curr], arr[leftChild]);
curr = leftChild;
leftChild = curr * 2;
rightChild = curr * 2 + 1;
}
}
}
}
void init(int arr[]){
for(int i = 0 ; i < s; i++){
arr[i] = -1;
}
}
int main(){
int arr[s];
init(arr);
insert(arr, 8);
insert(arr, 3);
insert(arr, 7);
insert(arr, 12);
insert(arr, 5);
insert(arr, 2);
insert(arr, 9);
insert(arr, 14);
insert(arr, 1);
del(arr, arr[1]);
for(int i = 1; i < s; i++){
if(arr[i] > 0)
printf("%d\n", arr[i]);
}
return 0;
}
Output :
2
5
3
12
8
7
9
14
2. Max Heap
Max heap adalah jenis heap dimana ia mengutamakan nilai yang paling besar. Jadi, root node akan selalu memiliki nilai terbesar di heap tersebut dan setiap child dari node akan mempunyai nilai lebih kecil daripada parent-nya.
Contoh Max Heap:
Insertion pada max heap adalah kebalikan dari insertion dalam min heap. Jika min heap akan melakukan swap jika parent-nya lebih besar, maka max heap akan melakukan swap jika parent-nya lebih kecil dan ia akan tetap mengecek sampai root node.
Deletion pada max heap mirip dengan min heap, kita delete node paling besar atau root node, lalu kita cari node terbesar dan melakukan swap dengan root node. Setelah itu jika ada node yang tidak memnuhi syarat, maka kita akan melakukan perjalanan kebawah dan melakukan penyesuaian pada heap kita.
Berikut adalah contoh code insertion dan deletion pada Max Heap:
Code :
#include <stdio.h>
const int s = 20;
int idx = 1;
void swap(int &a, int &b){
int temp = a;
a = b;
b = temp;
}
int upHeap(int arr[], int currIdx, int val){
int parent = currIdx / 2;
if(parent == 0){
return currIdx;
}
else if(arr[parent] < val){
swap(arr[parent], arr[currIdx]);
}
upHeap(arr, parent, val);
}
void insert(int arr[], int currIdx, int val){
if(currIdx > s-1) return;
arr[currIdx] = val;
upHeap(arr, currIdx, val);
idx++;
}
int downHeap(int arr[], int currIdx){
int lc = currIdx * 2;
int rc = currIdx * 2 + 1;
if(arr[lc] == -1 && arr[rc] == -1){
return currIdx;
}
else if(arr[lc] > arr[currIdx] && arr[rc] == -1){
swap(arr[lc], arr[currIdx]);
}
else if(arr[rc] > arr[currIdx] && arr[lc] == -1){
swap(arr[rc], arr[currIdx]);
}
else{
if(arr[rc] > arr[lc]){
swap(arr[currIdx], arr[rc]);
downHeap(arr, rc);
}
else if(arr[lc] > arr[rc]){
swap(arr[currIdx], arr[lc]);
downHeap(arr, lc);
}
}
return currIdx;
}
void remove(int arr[]){
if(idx == 1) return;
swap(arr[idx-1], arr[1]);
arr[idx-1] = -1;
idx--;
downHeap(arr, 1);
}
void init(int arr[]){
for(int i = 1; i < s; i++){
arr[i] = -1;
}
}
int main(){
int arr[s];
init(arr);
insert(arr, idx, 2);
insert(arr, idx, 5);
insert(arr, idx, 210);
insert(arr, idx, 220);
insert(arr, idx, 230);
insert(arr, idx, 250);
insert(arr, idx, 50);
insert(arr, idx, 60);
remove(arr);
for(int i = 1 ; i < s; i++){
if(arr[i] != -1)
printf("%d\n", arr[i]);
}
return 0;
}
Output :
230
220
50
60
210
5
2
3. Min-Max Heap
Min-Max Heap adalah gabungan dari min dan max heap, dimana setiap level dari tree akan berubah jenisnya.
Saya tidak punya code untuk min-max heap jika anda ingin mempelajari lebih lanjut tentang min-max heap saya merekomendasikan untuk mencari video di youtube tentang min-max heap.
No comments:
Post a Comment