#include<stdio.h>
#include<stdlib.h>
#include<limits.h>
int c,i,j;
int left(int j){return j*2+1;}
int right(int j){return j*2+2;}
int parent(int j) {return (j-1)/2;}
typedef struct node
{ int data;}node;
typedef struct heap
{ int capacity;
int heapSize;
node *element;
}heap;
void swap(node *x,node *y)
{ node *temp; temp=x; y=x; x=temp; }
initHeap(heap *h,int cap){h->capacity=cap;}
printHeap(heap *h){
for (i=0;i<h->capacity;i++)
printf("\n %d",h->element[i].data);
}
insertKey(heap *h,int k)
{
if(!(h->capacity))
h->element=malloc(sizeof(node));
else
h->element=realloc(h->element,(h->capacity+1)*sizeof(node));
node n;
n.data=k;
int i=(h->heapSize)++;
while(i&&h->element[i].data>h->element[parent(i)].data)
h->element[i]=h->element[parent(i)];
h->element[i]=n;
}
void heapify(heap *h,int i)
{
int max=i;
if(h->element[left(i)].data>h->element[i].data)
max=left(i);
if(h->element[right(i)].data>h->element[i].data)
max=right(i);
if(i!=max)
swap(&(h->element[max]),&(h->element[i]));
heapify(h,max);
}
int extractMax(heap *h)
{
int max=h->element[0].data;
h->element[0]=h->element[(h->heapSize)--];
h->element=realloc(h->element,h->heapSize*sizeof(node));
return max;
}
deleteKey(heap *h,int k)
{ if(h->heapSize)
{ h->element[k].data=INT_MAX;
heapify(h,k);
int d=extractMax(h);
}
else printf("\n MaxHeap Is Empty");
}
void main()
{
int capacity=0;
heap maxHeap;
initHeap(&maxHeap,capacity);
char c='c';
int key;
while (c=='c')
{ printf("\ni...insert");
printf("\np...print");
printf("\nm...get max");
printf("\ne...exit");
printf("\n\n........ENTER CHOICE::");
c=getchar();
switch (c)
{
case 'i' :
printf("\nEnter the number to be inserted : ");
scanf("%d",&key);
insertKey(&maxHeap,key);
printf("\n");
printHeap(&maxHeap);
break;
case 'p':
printf("\n");
printHeap(&maxHeap);
break;
case 'm':
printf("%d",extractMax(&maxHeap));
default : break;
}
printf("\nPress....c...To Continue");
printf("\nPress....any other key...EXIT");
c=getchar();
printf("\n");
}
}
#include<stdlib.h>
#include<limits.h>
int c,i,j;
int left(int j){return j*2+1;}
int right(int j){return j*2+2;}
int parent(int j) {return (j-1)/2;}
typedef struct node
{ int data;}node;
typedef struct heap
{ int capacity;
int heapSize;
node *element;
}heap;
void swap(node *x,node *y)
{ node *temp; temp=x; y=x; x=temp; }
initHeap(heap *h,int cap){h->capacity=cap;}
printHeap(heap *h){
for (i=0;i<h->capacity;i++)
printf("\n %d",h->element[i].data);
}
insertKey(heap *h,int k)
{
if(!(h->capacity))
h->element=malloc(sizeof(node));
else
h->element=realloc(h->element,(h->capacity+1)*sizeof(node));
node n;
n.data=k;
int i=(h->heapSize)++;
while(i&&h->element[i].data>h->element[parent(i)].data)
h->element[i]=h->element[parent(i)];
h->element[i]=n;
}
void heapify(heap *h,int i)
{
int max=i;
if(h->element[left(i)].data>h->element[i].data)
max=left(i);
if(h->element[right(i)].data>h->element[i].data)
max=right(i);
if(i!=max)
swap(&(h->element[max]),&(h->element[i]));
heapify(h,max);
}
int extractMax(heap *h)
{
int max=h->element[0].data;
h->element[0]=h->element[(h->heapSize)--];
h->element=realloc(h->element,h->heapSize*sizeof(node));
return max;
}
deleteKey(heap *h,int k)
{ if(h->heapSize)
{ h->element[k].data=INT_MAX;
heapify(h,k);
int d=extractMax(h);
}
else printf("\n MaxHeap Is Empty");
}
void main()
{
int capacity=0;
heap maxHeap;
initHeap(&maxHeap,capacity);
char c='c';
int key;
while (c=='c')
{ printf("\ni...insert");
printf("\np...print");
printf("\nm...get max");
printf("\ne...exit");
printf("\n\n........ENTER CHOICE::");
c=getchar();
switch (c)
{
case 'i' :
printf("\nEnter the number to be inserted : ");
scanf("%d",&key);
insertKey(&maxHeap,key);
printf("\n");
printHeap(&maxHeap);
break;
case 'p':
printf("\n");
printHeap(&maxHeap);
break;
case 'm':
printf("%d",extractMax(&maxHeap));
default : break;
}
printf("\nPress....c...To Continue");
printf("\nPress....any other key...EXIT");
c=getchar();
printf("\n");
}
}