binaryheap.cpp

#include <iostream>
using namespace std;
class minheap{
public:
 int *arr;
int capacity;
int len;
 
minheap(int l);
void insert(int);
int parent(int);    //index passed
void heapify(int);  //index passed,bottom up heapify
void delmin();
void changekey(int,int);
void topdownheapify(int);
void viewheap();
int getmin();
void del(int); //deleting arbritrary element,index passed
int leftchild(int);
int rightchild(int);
};

minheap::minheap(int l)
	{
	len=0;
	capacity=l;
	arr=new int[capacity];
	}
	
void minheap::insert(int element)
	{
	if(len==capacity)
		{	cout<<"no space";
		}
	else
		{
			len++;
			arr[len-1]=element;
			heapify(len-1);
		}
	}

int minheap::parent(int l)
	{
	return (l-1)/2;
	}

void minheap::heapify(int l)
	{
	int p=parent(l);
	while(l>=0 && arr[p]>arr[l])
		{
		int temp=arr[l];
		arr[l]=arr[p];
		arr[p]=temp;
		l=p;
		p=(l-1)/2;
	}

	}

int minheap::getmin()
	{
	return arr[0];
	}

void minheap::del(int i)
	{
	changekey(i,getmin()-1);
	delmin();
	}

void minheap::changekey(int index,int value)
	{
	int p=arr[index];
	arr[index]=value;
	if(p<value)
	topdownheapify(index);
	else
	heapify(index);
	}

void minheap::delmin()
	{
	
	arr[0]=arr[len-1];
	len--;
        topdownheapify(0);
	}
int minheap::leftchild(int n)
{
return 2*n+1;
}


int minheap::rightchild(int n)
{
return 2*n+2;
}
void minheap::topdownheapify(int i)
	{
          int j,l=leftchild(i);
	  int r=rightchild(i);
          while(l<len)
	{
	if(arr[l]<arr[r])
	j=l;
	else
	j=r;
	if(arr[j]<arr[i])
		{
		int temp=arr[j];
		arr[j]=arr[i];
		arr[i]=temp;
		i=j;
		l=leftchild(i);
		r=rightchild(i);
		}
	else
	break;
	}

	if(l==len-1)
	if(arr[l]<arr[i])
	{
                int temp=arr[l];
		arr[l]=arr[i];
		arr[i]=temp;
	}
	}

void minheap::viewheap()
	{
	for(int i=0;i<len;i++)
	cout<<arr[i]<<" ";
	cout<<"\n";
	}


int main()
{
int arr[]={10,98,94,65,35,75,25,55};
minheap h(100);
for(int i=0;i<8;i++)
h.insert(arr[i]);
h.viewheap();
h.delmin();
h.viewheap();
h.del(1);
h.viewheap();
return 0;
}