HEAPS
Pengertian
Heap merupakan sebuah konsep dalam data structure yang bisa direpresentasikan dalam beberapa cara, salah satunya dengan binary tree.berikut adalah heap dengan binary tree:
Heap dibagi menjadi 3, yaitu:
- Min Heap
- Max Heap
- Min-Max Heap
Min Heap
Min Heap adalah jenis heap yang menjadikan nilai paling kecil sebagai rootnya. Ini berarti semua child dari root pada min heap nilainya lebih besar daripada rootnya.
Dapat dilihat 1 sebagai root paling kecil daripada anak-anaknya.
Dalam melakukan insertion pada min heap, yang perlu diperhatikan adalah childnya harus lebih kecil daripada parent. jadi, saat insertion perlu dilakukan compare antara nilai yang ingin di insert. Jika value yang diinsert lebih kecil, kita akan melakukan swap dan menukar nilai. Proses ini berlanjut hingga kita mengcompare dengan root node.
Dalam melakukan deletion, yang di delete adalah root node atau node dengan nilai terkecil. node paling bawah dan paling kanan akan menggantikan root, lalu perbaiki rootnya jika menyalahi aturan min heap dengan swap berulang-ulang.
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
Max Heap
Max heap adalah jenis heap yang berkebalikan dengan min heap. pada max heap nilai terbesar menjadi root pada tree dan nilai yang lebih kecil menjadi anaknya.
9 adalah nilai terbesar dan ia adalah root
untuk insertion dan deletion konsepnya sama seperti min heap, bedanya adalah syaratnya harus rootnya yang paling besar.
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
Min-Max Heap
pada min max heap, pada setiap level dari tree akan berbeda-beda jenisnya. maksudnya jika pada level pertama heap min, maka level selanjutnya max.
8 min, 71 dan 41 max, dan seterusnya...
maksudnya adalah jika parent min, anak max. jika parent max, maka anak min. Terima Kasih....
Komentar
Posting Komentar