Tuesday 7 March 2017

insert and deletemin operation in binary heap : c program

#include <stdio.h>
#include <stdlib.h>
int LeftChild(int);
void heapify(int *,int,int);
void Build_maxheap(int *,int);
int insert(int *,int,int);
main()
{
 int n,i,a[100],opt,val;
 printf("enter n value");
 scanf("%d",&n);
 for(i=0;i<n;i++)      //reading values into array
  scanf("%d",&a[i]);
 Build_maxheap(a,n);   //building max heap
 printf("\n max heap\n"); // printing max heap
 for(i=0;i<n;i++)
  printf("%d\t",a[i]);
while(1)
{
 printf("\nPress 1. Insert \t 2. DeleteMax \t 3. exit\n");
 scanf("%d",&opt);
 switch(opt)
 {
  case 1: printf("\nenter the value to insert\n");
    scanf("%d",&val);
    n=insert(a,val,n);
    printf("\nafter inserting\n");
    for(i=0;i<n;i++)
     printf("%d\t",a[i]);
    break;
      
  case 2: DeleteMax(a,n);
    printf("\nafter deleting\n");
    for(i=0;i<n;i++)
     printf("%d\t",a[i]);
    break;
  case 3: exit(0);
 }
}
}
int insert(int *a,int val,int n)
{
 int k,t,i;
 a[n]=val;

 for(k=n;(k-1)/2>=0;k=(k-1)/2)
 {
  if(a[k]>a[(k-1)/2])
  {
   t=a[k];
   a[k]=a[(k-1)/2];
   a[(k-1)/2]=t;
  }
  else
   break;
 }
 n=n+1;
 return n;
}
int DeleteMax(int *a, int n)
{
 int max;
 if(n<1)
 {
  printf("no elements to delete");
 }
 else
 {
  max=a[0];
  printf("deleted maximum = %d",max);
  a[0] = a[n-1];
   heapify(a,0,n-1);
  n=n-1;
  return n;
 }
}
int LeftChild(int i)
{
 return (2*(i)+1);
}
void heapify(int *a,int j, int n)
{
 int bci,t;
 for(;LeftChild(j) <n;j=bci) //as long as left child exists
 {
  bci=LeftChild(j); //bci means biggest child index
  if( bci != n-1 &&  a[bci+1] > a[bci])//bci+1 means right child index of i
    bci= bci+1;

  if(a[bci]> a[j])// if big child value is > parent, swap big child value and parent value.
   {
    t=a[j];
    a[j]=a[bci];
    a[bci]=t;
   }
  else    //if big child value is < parent, then this is following max heap property
   break;
 }
   
}
void Build_maxheap(int *a, int n)
{
 int i;
 for(i=n/2;i>=0;i--)// loop for converting complete binary tree to max heap
  heapify(a,i,n);
}

Output:

No comments:

Post a Comment