Computer Science‎ > ‎

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;
}


Testing Zone For Programmers- 

Try out our online Multiple-Choice-Question tests in Programming and Computer Science!



Photo-credits: www.istockphoto.com

 Quizzes on Basic Object Oriented Programming with C++   Quizzes on Java Programming
 Quizzes on C Programming- Arrays, Strings and Pointers
  1. C Programming MCQ Quiz #1:  Strings- 1
  2. C Programming MCQ Quiz #2: Strings (2)
  3. C Programming MCQ Quiz #3: Strings (3)
  4. C Programming MCQ Quiz #4: Arrays(1)
  5. C Programming MCQ Quiz #5: Arrays (2)
  6. C Programming MCQ Quiz #6: Arrays (3)
  7. C Programming MCQ Quiz #7: Pointers (1)
  8. C Programming MCQ Quiz #8: Pointers (2)
 Quizzes on Data Structures, Algorithms and Complexity
  1. MCQ Quiz #1: The Basics of Sorting Algorithms- Quadratic Sorts
  2. MCQ Quiz #2: Efficient Sorting Algorithms- Quick sort, Merge Sort, Heap Sort
  3. MCQ Quiz #3- The Radix Sort
  4. MCQ Quiz #4: Divide and Conquer Techniques- Binary Search, Quicksort, Merge sort, Complexities
  5. MCQ Quiz #5- Dynamic Programming
  6. MCQ Quiz #6- Complexity of Algorithms
  7. MCQ Quiz #7- Application of Master's Theorem
  8. MCQ Quiz #8: Binary Search Trees
  9. MCQ Quiz #9: B-Trees
  10. 10 MCQ Quiz #9: AVL-Trees
  11. 11 MCQ Quiz #10: Representing Graphs as Data Structures
  12. 12 MCQ Quiz #11: Spanning Trees
  13. 13 MCQ Quiz #12: Algorithms - Graphs: Spanning Trees - Kruskal and Prim Algorithms
  14. 14 MCQ Quiz #13: Algorithms - Graphs: Depth and Breadth First Search