MIN HEAP C++ IMPLEMENTATION FROM SCRATCH
#include<iostream>
#include<math.h>
using namespace std;
class Heap{
int top,*a,cap,i,j;
public:
Heap(int c){
cap = c+1;
a = new int[cap];
top=1;
for(i=0;i<cap;i++) a[i]=INT_MAX;
}
void insert(int val);
void deletemin();
void display();
};
void Heap::insert(int val){
if(top==cap){
cout<<"Over-Flow"<<endl;
return;
}else{
a[top] = val;
if(top==1){
top++;
return;
}
i = top;
j = floor(i/2);
while(a[i]<a[j] && j>0){
swap(a[i],a[j]);
i = j;
j = floor(j/2);
}
top++;
}
}
void Heap::deletemin(){
if(top==1){
cout<<"Under-Flow"<<endl;
return;
}else{
cout<<a[1]<<" is deleted"<<endl;
a[1]=a[top-1];
a[top-1]=INT_MAX;
top--;
cout<<a[1]<<endl;
i = top-1;
j = 0;
while(i>1){
i = i/2;
j++;
}
j = pow(2,j);
i=1;
while((a[i]>a[2*i] || a[i]>a[(2*i)+1]) && i<j){
if(a[2*i] >a [(2*i)+1]){
swap(a[i],a[(2*i)+1]);
i = (2*i)+1;
}else{
swap(a[i],a[(2*i)]);
i = (2*i);
}
}
}
}
void Heap::display(){
cout<<"\n---------------------\n Heap \n---------------------\n"<<endl;
for(int k=1;k<top;k++) cout<<a[k]<<" ";
cout<<endl<<endl;
}
int main(){
int c,ch,val;
cout<<"Enter Heap Size:";cin>>c;
Heap obj(c);
do{
cout<<"1.Insert\n2.Delete Min\n3.Display\n5.Exit"<<endl;
cout<<"Enter your choice:";cin>>ch;
switch(ch){
case 1:
cout<<"Enter Element to insert:";cin>>val;
obj.insert(val);
break;
case 2:
obj.deletemin();
break;
case 3:
obj.display();
break;
case 5:
break;
default:
cout<<"Re-Enter"<<endl;
}
}while(ch!=5);
}
#include<math.h>
using namespace std;
class Heap{
int top,*a,cap,i,j;
public:
Heap(int c){
cap = c+1;
a = new int[cap];
top=1;
for(i=0;i<cap;i++) a[i]=INT_MAX;
}
void insert(int val);
void deletemin();
void display();
};
void Heap::insert(int val){
if(top==cap){
cout<<"Over-Flow"<<endl;
return;
}else{
a[top] = val;
if(top==1){
top++;
return;
}
i = top;
j = floor(i/2);
while(a[i]<a[j] && j>0){
swap(a[i],a[j]);
i = j;
j = floor(j/2);
}
top++;
}
}
void Heap::deletemin(){
if(top==1){
cout<<"Under-Flow"<<endl;
return;
}else{
cout<<a[1]<<" is deleted"<<endl;
a[1]=a[top-1];
a[top-1]=INT_MAX;
top--;
cout<<a[1]<<endl;
i = top-1;
j = 0;
while(i>1){
i = i/2;
j++;
}
j = pow(2,j);
i=1;
while((a[i]>a[2*i] || a[i]>a[(2*i)+1]) && i<j){
if(a[2*i] >a [(2*i)+1]){
swap(a[i],a[(2*i)+1]);
i = (2*i)+1;
}else{
swap(a[i],a[(2*i)]);
i = (2*i);
}
}
}
}
void Heap::display(){
cout<<"\n---------------------\n Heap \n---------------------\n"<<endl;
for(int k=1;k<top;k++) cout<<a[k]<<" ";
cout<<endl<<endl;
}
int main(){
int c,ch,val;
cout<<"Enter Heap Size:";cin>>c;
Heap obj(c);
do{
cout<<"1.Insert\n2.Delete Min\n3.Display\n5.Exit"<<endl;
cout<<"Enter your choice:";cin>>ch;
switch(ch){
case 1:
cout<<"Enter Element to insert:";cin>>val;
obj.insert(val);
break;
case 2:
obj.deletemin();
break;
case 3:
obj.display();
break;
case 5:
break;
default:
cout<<"Re-Enter"<<endl;
}
}while(ch!=5);
}
Comments
Post a Comment