Heap Data Structures -with C Program source code

To go through the C program / source-code, scroll down to the end of this page

Heap

The Heap data structure is an array object that can be viewed as a complete and balanced binary tree. Min (Max)-Heap has a property that for every node other than the root, the value of the node is at least (at most) the value of its parent. Thus, the smallest (largest) element in a heap is stored at the root, and the sub-trees rooted at a node contain larger (smaller) values than does the node itself.

A Min-heap viewed as a binary tree and an array. Heaps can be used as an array. For any element at array position I, left child is at ( 2i ), right child is at ( 2i+1 ) and parent is at (int) (i / 2). Heap size is stored at index 0.

Basic operations of a heap are:

1. Insert – Insert an element.

2. Delete minimum – Delete and return the smallest item in the heap.

Performance

1. Worst case complexity of Insert is O (lg n), where n is the number of elements in the heap.

2. Worst case running time of DeleteMin is O (lg n) where n is the number of elements in the heap.

Complete Tutorial with Example :

Using Heaps for Heap Sort - C Program Source Code

#include<stdio.h>
#include<limits.h>
/*Declaring heap globally so that we do not need to pass it as an argument every time*/
/* Heap used here is Min Heap */
int heap[1000000],heapSize;
/*Initialize Heap*/
void Init()
{
        heapSize = 0;
        heap[0] = -INT_MAX;
}
/*Insert an element into the heap */
void Insert(int element)
{
        heapSize++;
        heap[heapSize] = element; /*Insert in the last place*/
        /*Adjust its position*/
        int now = heapSize;
        while(heap[now/2] > element) 
        {
                heap[now] = heap[now/2];
                now /= 2;
        }
        heap[now] = element;
}
int DeleteMin()
{
        /* heap[1] is the minimum element. So we remove heap[1]. Size of the heap is decreased. 
           Now heap[1] has to be filled. We put the last element in its place and see if it fits.
           If it does not fit, take minimum element among both its children and replaces parent with it.
           Again See if the last element fits in that place.*/
        int minElement,lastElement,child,now;
        minElement = heap[1];
        lastElement = heap[heapSize--];
        /* now refers to the index at which we are now */
        for(now = 1; now*2 <= heapSize ;now = child)
        {
                /* child is the index of the element which is minimum among both the children */ 
                /* Indexes of children are i*2 and i*2 + 1*/
                child = now*2;
                /*child!=heapSize beacuse heap[heapSize+1] does not exist, which means it has only one 
                  child */
                if(child != heapSize && heap[child+1] < heap[child] ) 
                {
                        child++;
                }
                /* To check if the last element fits ot not it suffices to check if the last element
                   is less than the minimum element among both the children*/
                if(lastElement > heap[child])
                {
                        heap[now] = heap[child];
                }
                else /* It fits there */
                {
                        break;
                }
        }
        heap[now] = lastElement;
        return minElement;
}
int main()
{
        int number_of_elements;
        scanf("%d",&number_of_elements);
        int iter, element;
        Init();
        for(iter = 0;iter < number_of_elements;iter++)
        {
                scanf("%d",&element);
                Insert(element);
        }
        for(iter = 0;iter < number_of_elements;iter++)
        {
                printf("%d ",DeleteMin());
        }
        printf("\n");
        return 0;
}