Min-Heap Implementation
AIM:
To Implement a Min-Heap
Description:
In this program, Min-Heap is implemented using arrays
Program:
#include<stdio.h>
#include<stdlib.h>
void swap(int *a,int *b)
{
int temp=*b;
*b=*a;
*a=temp;
}
void heapify(int arr[],int size,int i)
{
if(size==1)
{
printf("\n Single Element in the Heap %d",arr[0]);
}
else
{
int smallest=i;
int l=2*i+1;
int r=2*i+2;
if(l<size&&arr[l]<arr[i])
smallest=l;
if(r<size&&arr[r]<arr[smallest])
smallest=r;
if(smallest!=i)
{
swap(&arr[i],&arr[smallest]);
heapify(arr,size,smallest);
}
}
}
void insert(int arr[],int num,int size)
{
int i;
if(size==0)
{
arr[0]=num;
}
else
{
arr[size]=num;
for(i=size/2-1;i>=0;i--)
{
heapify(arr,size,i);
}
}
}
int delete(int arr[],int size,int num)
{
int i;
for(i=0;i<size;i++)
{
if(num==arr[i])
break;
}
if(i==size)
{
return -1;
}
swap(&arr[i],&arr[size-1]);
size=size-1;
for(i=size/2-1;i>=0;i--)
{
heapify(arr,size,i);
}
return num;
}
void printMinHeap(int arr[],int size)
{
int i;
for(i=0;i<size;i++)
{
printf(" %d",arr[i]);
}
printf("\n");
}
int main()
{
int cho,num,ans,arr[1000],size=0;
printf("\n Enter Operation to be performed : ");
printf("\n 1. Insertion");
printf("\t 2. Deletion");
printf("\t 3. Print Min Heap");
printf("\t 4. Exit");
do
{
printf("\n Enter Your Choice : ");
scanf("%d",&cho);
switch(cho)
{
case 1:
printf("\n Enter Number to be Inserted : ");
scanf("%d",&num);
insert(arr,num,size);
size=size+1;
printf("\n Number %d Inserted!!!\n",num);
break;
case 2:
printf("\n Enter Number to be Deleted : ");
scanf("%d",&num);
ans=delete(arr,size,num);
if(ans==-1)
{
printf("\n Number haven't found!!!\n");
}
else
{
printf("\n Number %d Deleted!!\n",ans);
size=size-1;
}
break;
case 3:
printf("\n Min-Heap: \n");
printMinHeap(arr,size);
break;
case 4:
printf("\n Done!!!\n");
break;
default:
printf("\n Invalid Choice!!!\n");
}
}while(cho!=4);
return 0;
}
OUTPUT
Enter Operation to be performed :
1. Insertion 2. Deletion 3. Print Min Heap 4. Exit
Enter Your Choice : 1
Enter Number to be Inserted : 10
Number 10 Inserted!!!
Enter Your Choice : 1
Enter Number to be Inserted : 20
Number 20 Inserted!!!
Enter Your Choice : 1
Enter Number to be Inserted : 32
Number 32 Inserted!!!
Enter Your Choice : 1
Enter Number to be Inserted : 56
Number 56 Inserted!!!
Enter Your Choice : 1
Enter Number to be Inserted : 48
Number 48 Inserted!!!
Enter Your Choice : 1
Enter Number to be Inserted : 8
Number 8 Inserted!!!
Enter Your Choice : 1
Enter Number to be Inserted : 64
Number 64 Inserted!!!
Enter Your Choice : 3
Min-Heap:
8 20 10 56 48 32 64
Enter Your Choice : 2
Enter Number to be Deleted : 32
Number 32 Deleted!!
Enter Your Choice : 2
Enter Number to be Deleted : 56
Number 56 Deleted!!
Enter Your Choice : 3
Min-Heap:
8 20 10 64 48
Enter Your Choice : 2
Enter Number to be Deleted : 8
Number 8 Deleted!!
Enter Your Choice : 3
Min-Heap:
10 20 48 64
Enter Your Choice : 4
Done!!!
--------------------------------
Process exited after 2.365 seconds with return value 0
Press any key to continue . . .
No comments:
Post a Comment