BINARY HEAP

A binary heap is a heap data structure created using a binary tree. It can be seen as a binary tree with two additional constraints:

• The shape property: the tree is a complete binary tree; that is, all levels of the tree, except possibly the last one (deepest) are fully filled, and, if the last level of the tree is not complete, the nodes of that level are filled from left to right.
• The heap property: each node is greater than or equal to each of its children according to some comparison predicate which is fixed for the entire data structure.

"Greater than or equal to" means according to whatever comparison function is chosen to sort the heap, not necessarily "greater than or equal to" in the mathematical sense (since the quantities are not always numerical). Heaps where the comparison function is mathematical "greater than or equal to" are called max-heaps; those where the comparison function is mathematical "less than" are called "min-heaps". Conventionally, min-heaps are used, since they are readily applicable for use in priority queues.

Note that the ordering of siblings in a heap is not specified by the heap property, so the two children of a parent can be freely interchanged, as long as this does not violate the shape and heap properties (compare with treap).

The binary heap is a special case of the d-ary heap in which d = 2.

It is possible to modify the heap structure to allow extraction of both the smallest and largest element in O(logn) time. To do this, the rows alternate between min heap and max heap. The algorithms are roughly the same, but, in each step, one must consider the alternating rows with alternating comparisons. The performance is roughly the same as a normal single direction heap. This idea can be generalised to a min-max-median heap.

----------------------------------------------------------------------------------------------

A C PROGRAM TO IMPLEMENT OPERATIONS IN BINARY HEAP

COMPILER EMPLOYED: DEV C++ COMPILER-4.9.9.2

SOURCE FILE SIZE :2 kb

EXE FILE SIZE :22 kb

NOTE: PLEASE INCLUDE THE DESIRED HEADER FILE

---------------------------------------------------------------------------------------------

C PROGRAM SOURCE & EXE DOWNLOAD:

Click download button to download

DISCLAIMER: The following program cannot be ensured of perfection.so any flaws in the program can be notified in the comments section.

----------------------------------------------------------------------------------------------

CODE:

#include
int heap[10],min,last,h=0;
void insert();
void deletemin();
void display();
int main()
{
int CH,OPT;

do
{

printf("\n BINARY HEAP-ARRAY IMPLEMENTATION");
printf("\n\n NOTE:ARRAY MAXIMUM SIZE DEFINED:10");
printf("\n\n MENU:");
printf("\n [1].INSERT");
printf("\n [2].DELETEMIN");
printf("\n [3].DISPLAY");
printf("\n [4].EXIT");
printf("\n\n OPTION:");
scanf("%d",&OPT);

switch(OPT)
{
case 1:
insert();
break;

case 2:
deletemin();
break;

case 3:
display();
break;

case 4:
break;


}
printf("\n DO YOU WISH TO CONTINUE?1~0:");
scanf("%d",&CH);
}while(CH==1);
printf("\n\n");
system("pause");
return 0;
}

void insert()
{
int i,x;
printf("\nINSERTION MECHANISM LAUNCHED");
if( h>9)
printf("\n HEAP IS FULL");
else
{
h++;
printf("\n ENTER ELEMENT TO BE INSERTED:");
scanf("%d",&x);
for(i=h;heap[i/2]>x;i=i/2)
{
heap[i]=heap[i/2];
}
heap[i]=x;
}
}

void deletemin()
{
int i,child;
if(h==0)
printf("\n\n HEAP IS EMPTY...");
else
{
min=heap[i];
last=heap[h];
h--;
for(i=1;i*2<=h;i=child) { child=i*2; if(child!=h&&heap[child-1]heap[child])
heap[i]=heap[child];
else
break;
}
heap[i]=0;
}
printf("\n MINIMUM ELEMENT DELETED SUCCESSFULLY...");
}
}


void display()
{
int i;
if(h==0)
printf("\nQUESUE IS EMPTY...");
else
for(i=0;i<10;i++)

printf("%d\n",heap[i]);

}

----------------------------------------------------------------------------------------------

Your's friendly,
[MOHANRAM.G],
ADMIN...