C Program to implement Bottom Up Heap Construction Algorithm

By | April 28, 2017

Bottom Up Heap Construction Algorithm


Write a C Program to implement Bottom Up Heap Construction Algorithm. Here’s simple Program to Build Max Heap using Bottom Up Approach in C Programming Language.


What is Heap ?


Heap is a special case of balanced binary tree data structure where the root-node key is compared with its children and arranged accordingly. If α has child node β then −

  • key(α) ≥ key(β)

As the value of parent is greater than that of child, this property generates Max Heap.


Below is the source code for C Program to implement Bottom Up Heap Construction Algorithm which is successfully compiled and run on Windows System to produce desired output as shown below :


SOURCE CODE : :


/* C Program to implement Bottom Up Heap Construction Algorithm */

#include <stdio.h>
#include <stdlib.h>

#define MAX_VAL 9999

void restoreDown(int arr[], int i, int size);
void buildHeap(int arr[], int size );
void display(int arr[],int hsize);

int main( )
{
	int arr[100]; /*array used to represent heap*/
	int hsize=0;  /*Number of nodes in the heap*/
	int i,choice,num;

	arr[0]= MAX_VAL;

	while(1)
	{
	    printf("\n1.Build Heap\n");
		printf("2.Display\n");
		printf("3.Exit\n");
		printf("\nEnter your choice : ");
		scanf("%d",&choice);
		switch(choice)
		{

 		 case 1:
			printf("\nEnter size of the array :: ");
			scanf("%d",&hsize);
			printf("\nEnter array Elements :: \n");

			for(i=1;i<=hsize;i++)
            {
                printf("\nEnter %d Element : ",i);
                scanf("%d",&arr[i]);
            }


			buildHeap(arr,hsize);
			break;

        case 2:
            printf("\n");
			display(arr,hsize);
			printf("\n");
			break;


		 case 3:
			exit(1);

		 default:
			printf("\nWrong choice\n");

		}/*End of switch */
	}/*End of while */

	return 0;

}/*End of main( )*/

void restoreDown(int arr[], int i, int hsize )
{
	int lchild=2*i, rchild=lchild+1;

	int num=arr[i];

	while( rchild <= hsize )
	{
		if( num>=arr[lchild] && num>=arr[rchild] )
		{
			arr[i] = num;
			return;
		}
		else if(arr[lchild] > arr[rchild])
		{
			arr[i] = arr[lchild];
			i = lchild;
		}
		else
		{
			arr[i] = arr[rchild];
			i = rchild;
		}
		lchild = 2 * i;
		rchild = lchild + 1;
	}
	/*If number of nodes is even*/
	if(lchild == hsize && num < arr[lchild] )
	{
		arr[i]=arr[lchild];
		i = lchild;
	}
	arr[i]=num;
}/*End of restoreDown()*/


void display(int arr[],int hsize)
{
	int i;
	if(hsize==0)
	{
		printf("\nHeap is empty\n");
		return;
	}
	for(i=1;i<=hsize;i++)
		printf("%d ",arr[i]);
	printf("\n");

	printf("\nNumber of elements = %d\n",hsize);
}/*End of display( )*/

/*Bottom up approach*/
 void buildHeap(int arr[], int size )
{
	int i;
	for(i=size/2; i>=1; i--)
		restoreDown(arr,i,size);
}

OUTPUT : :


/* C Program to implement Bottom Up Heap Construction Algorithm */

1.Build Heap
2.Display
3.Exit

Enter your choice : 1

Enter size of the array :: 10

Enter array Elements ::

Enter 1 Element : 4

Enter 2 Element : 1

Enter 3 Element : 6

Enter 4 Element : 9

Enter 5 Element : 11

Enter 6 Element : 23

Enter 7 Element : 12

Enter 8 Element : 6

Enter 9 Element : 5

Enter 10 Element : 0

1.Build Heap
2.Display
3.Exit

Enter your choice : 2

23 11 12 9 1 6 4 6 5 0

Number of elements = 10


1.Build Heap
2.Display
3.Exit

Enter your choice : 3

Process returned 1

If you found any error or any queries related to the above program or any questions or reviews , you wanna to ask from us ,you may Contact Us through our contact Page or you can also comment below in the comment section.We will try our best to reach up to you in short interval.


Thanks for reading the post….

Leave a Reply