Sunday, September 6, 2015

Program to Build binary MaxHeap using ANSI C

#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");
}
 

}