DATA STRUCTURES-POINTER IMPLEMENTATION OF HEAPS

PROGRAM CODING:-

#include<stdio.h>
#include<stdlib.h>
struct heap
{
int cap,size;
int *arr;
};
struct heap * initialize(int max)
{
struct heap *h;
h=(struct heap *)malloc(sizeof(struct heap));
h->arr=(int *)malloc((max+1)*sizeof(int));//no element stored at position 0.
h->cap=max;
h->size=0;
h->arr[0]=-999;
return h;
}
int isempty(struct heap * h)
{
return(h->size==0);
}
int isfull(struct heap * h)
{
return(h->size==h->cap);
}
void insert(int x,struct heap **h)
{
int i;
for(i=++(*h)->size;(*h)->arr[i/2]>x;i/=2)
(*h)->arr[i]=(*h)->arr[i/2];
(*h)->arr[i]=x;
}
int deletemin(struct heap **h)
{
int i,child;
int min,last;
min=(*h)->arr[1];
last=(*h)->arr[(*h)->size--];
for(i=1;i*2<=(*h)->size;i=child)
{
child=i*2;
if(child!=(*h)->size && (*h)->arr[child+1]<(*h)->arr[child])
child++;
if(last>(*h)->arr[child])
(*h)->arr[i]=(*h)->arr[child];
else
break;
}
(*h)->arr[i]=last;
return min;
}
struct heap * makeempty(struct heap *h,int max)
{
h=initialize(max);
return h;
}
void dispose(struct heap *h,int max)
{
h=makeempty(h,max);
free(h);
}
struct heap * heapsort(struct heap *h)
{
struct heap * h1;
int k,i;
h1=initialize(h->cap);
h1->size=h->size;
printf("After performing heapsort on the contents of the priority queue \n");
for(i=1;i<=h1->size;i++)
{
k=deletemin(&h);
h1->arr[i]=k;
printf("%d\t",h1->arr[i]);
}
dispose(h,h1->cap);
return h1;
}
void display(struct heap *h)
{
int i;
if(isempty(h))
{
printf("Heap is empty!**!");
return;
}
printf("The elements of the queue are: \n");
for(i=1;i<=h->size;i++)
printf("%d\t",h->arr[i]);
}
int findmin(struct heap *h)
{
return h->arr[1];
}
int main()
{
struct heap *h;
int ch,data,n;
printf("Enter the size of the priority queue: ");
scanf("%d",&n);
h=initialize(n);
while(1)
{
printf("\nPRIORITY QUEUE MENU:\n\t1.Insert\n\t2.Delete min\n\t3.Heap sort\n\t4.Find min\n\t5.Make empty\n\t6.Delete Queue and exit\nChoice:");
scanf("%d",&ch);
switch(ch)
{
case 1:
if(isfull(h))
printf("Fatal Error:Priority Queue is full!**!");
else
{
printf("Enter the element to be inserted: ");
scanf("%d",&data);
insert(data,&h);
display(h);
}
break;
case 2:
if(isempty(h))
printf("Fatal Error:Priority Queue is empty!**!");
else
{
deletemin(&h);
display(h);
}
break;
case 3:
if(isempty(h))
printf("Sort not possible-Queue is empty");
else
h=heapsort(h);
break;
case 4:
if(isempty(h))
printf("Fatal Error:Priority Queue is empty!**!");
else
printf("Minimum element is : %d",findmin(h));
break;
case 5:
if(isempty(h))
printf("Priority Queue is already empty!**!");
else
{
h=makeempty(h,n);
printf("Priority Queue made empty!**!");
}
break;
case 6:
dispose(h,n);
return 1;
default:printf("Enter correct menu option!**!");
}
}
return 0;
}