Heaps are one type of data structure where elements are stored in two fashions either every parent element is greater than their children or is smaller than their children. Below we will discuss the two fashions.
Max-Heap
A max heap is a complete binary tree such that for each node, the key value in the node is greater than or equal to the value in its children. Observe that this implies that the root contains the largest value in the tree.
Min-Heap
A min-heap is a complete binary tree such that for each node, the key value in the node is smaller than or equal to the value in its children. Observe that this implies that the root contains the smallest value in the tree which is shown in the following Figure.
In either case of the above said two types of the heap the binary tree will grow in that way: parent(2*i),left-child(2*i+1), and right-child(2*i+2), where i ∈ [0,n]. When we insert or delete an element every time we have to maintain the heap property. Below we will give an example to clarify the insertion and deletion where the MAX-HEAP property is maintained which is clearly shown in the following figures. Suppose we have a complete binary tree which is shown below.
When we delete always the root element will be deleted and after that we have to maintain the heap property so that the rest of the elements are properly placed. Below we will see a clear picture of deletion.
Source Code of Max-Heap
#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#define MAX 50
void insert(int *,int,int,int);
void down_adjust(int *,int);
void display(int *,int);
void del_hi_priori(int *,int,int);
void swap(int *,int *);
int main()
{
int *heap,n,i,lb,last,temp,choice,data;
heap=(int *)malloc(sizeof(int)*MAX);
n=0;
lb=0;
while(1)
{
printf("\n.....MAIN MENU.....");
printf("\n1.Insert");
printf("\n2.Delete");
printf("\n3.Display");
printf("\n4.Quit");
printf("\nEnter your choice : ");
scanf("%d",&choice);
switch(choice)
{
case 1:printf("\nEnter data to be inserted : ");
scanf("%d",&data);
insert(heap,n,data,lb);
n++;
break;
case 2:del_hi_priori(heap,n,0);
n--;
break;
case 3:display(heap,n);
break;
case 4:return 0;
}
}
return 0;
}
void insert(int *heap,int heapsize,int data,int lb)
{
int i,p;
int parent(int);
if(heapsize==MAX)
{
printf("Queue Is Full!!");
}
i=lb+heapsize;
heap[i]=data;
while(i>lb && heap[p=parent(i)]<heap[i])
{
swap(&heap[p],&heap[i]);
i=p;
}
}
void del_hi_priori(int *heap,int heapsize,int lb)
{
int i,t,p;
if(heapsize==0)
{
printf("Queue Is Empty!!");
}
t=heap[0];
printf("\nElement %d is deleted",t);
swap(&heap[0],&heap[heapsize-1]);
i=1;
while(i>lb && heap[p=parent(i)]<heap[i])
{
swap(&heap[p],&heap[i]);
i=p;
}
}
int parent(int i)
{
float p;
p=((float)i/2.0)-1.0;
return ceil(p);
}
void display(int *heap,int n)
{
int i;
if(n==0)
{
printf("Queue Is Empty!!");
}
for(i=0;i<n;i++)
printf("%d| ",heap[i]);
}
void swap(int*p,int*q)
{
int temp;
temp=*p;
*p=*q;
*q=temp;
}
Happy Exploring!
Posts
No comments:
Post a Comment