#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:
#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