Max Heap Implementation in C++

#include<iostream>
using namespace std ;
#include<malloc.h>

typedef struct HEAP
{
int *array ;
int capasity ;
int size ;
}heap ;

heap * create_max_heap(int ) ;
heap* insert_max_heap(heap *,int ) ;
int parent(int ) ;
void swap(int *,int *) ;
int delete_position(heap *,int ) ;
int extract_max(heap *) ;
void max_heapify(heap *,int ) ;
int left_child(int ) ;
int right_child(int ) ;
void display(heap *) ;

int main()
{
int no,ele,i ,choice,conti ;
heap *h ;
h=NULL ;

cout<<"\n enter the maximum capacity of the heap " ;
cin>>no ;
h=create_max_heap(no) ;

do
{
cout<<"\n 1. insert elements in the heap " ;
cout<<"\n 2. delete an elementfrom a required position from the heap " ;
cout<<"\n 3. extract the minimum element from the heap " ;
cout<<"\n 4. display the elements of the heap (as if in an array)" ;
cout<<"\n please enter your choice" ;
cin>>choice ;
switch(choice)
{
case 1 :cout<<"\n how many elements to insert in the heap " ;
cin>>no ;
cout<<"\n enter the elements" ;
for(i=0;i<no;i++)
{
cin>>ele ;
h=insert_max_heap(h,ele) ;
}
break ;
case 2 :cout<<"\n enter the position of element that need to be deleted " ;
cin>>no ;
ele=delete_position(h,no) ;
if(ele==-1)
cout<<"\n SORRY !!! heap is empty OR no such position is found in the heap  " ;
else
cout<<"\n element that is deleted from position = "<<no<<" from the heap id = "<<ele ; ;
break ;
case 3 :ele=extract_max(h) ;
if(ele==-1)
cout<<"\n SORRY !!! heap is empty " ;
else
cout<<"\n maximum element in the heap(extracted) = "<<ele ;
break ;
case 4 :display(h) ;
break ;
}
cout<<"\n enter 1 to continue " ;
cin>>conti ;
}while(conti==1) ;
return 0 ;
}

heap * create_max_heap(int cap)
{
heap *h ;
h=(heap*)malloc(sizeof(heap)) ;

h->capasity=cap ;
h->size=0 ;
h->array=(int*)malloc(h->capasity*sizeof(int)) ;
return h ;
}

heap* insert_max_heap(heap *h,int data)
{
if(h->capasity==h->size)
{
cout<<"\n HEAP OVERFLOW !!! no space to enter more number elements " ;
return h ;
}
int i ;
i=h->size ;
h->array[h->size++]=data ;

while(i!=0&&h->array[parent(i)]<h->array[i])
{
swap(&h->array[parent(i)],&h->array[i]) ;
i=parent(i) ;
}
return h ;
}

int parent(int i)
{
return (i-1)/2 ;
}

void swap(int *a,int *b)
{
int temp ;

temp=(*a) ;
(*a)=(*b) ;
(*b)=temp ;
}

int delete_position(heap *h,int no)
{
if(h->size==0)
return -1 ;
if(no>h->size)
return -1 ;
if(no==1)
return extract_max(h) ;

int ele ;
ele=h->array[no-1] ;
h->array[no-1]=h->array[h->size-1] ;
h->size-- ;
max_heapify(h,no) ;

return ele ;
}

int extract_max(heap *h)
{
if(h->size==0)
{
cout<<"\n HEAP UNDERFLOW !!! no element present to display " ;
return -1 ;
}
if(h->size==1)
{
return(h->array[--(h->size)]) ;
}

int ele ;
ele=h->array[0] ;
h->array[0]=h->array[--(h->size)] ;

max_heapify(h,0) ;
return ele ;
}

void max_heapify(heap *h,int p)
{
int left,right,big ;
left=left_child(p) ;
right=right_child(p) ;
big=p ;

if(left<h->size&&h->array[p]<h->array[left])
big=left ;
if(right<h->size&&h->array[right]>h->array[big])
big=right ;

if(big!=p)
{
swap(&(h->array[p]),&(h->array[big])) ;
max_heapify(h,big) ;
}
}

int left_child(int i)
{
return 2*i+1 ;
}

int right_child(int i)
{
return 2*i+2 ;
}

void display(heap *h)
{
int i ;
if(h->size==0)
{
cout<<"\n SORRY !!! heap is emplty no elememt to display" ;
return ;
}

for(i=0;i<h->size;i++)
cout<<h->array[i]<<" " ;

}