Max heap and min heap is a complete binary tree with special property.

  • Min Heap, A complete binary tree where each node value is less than or equal to it’s child node.
  • Max Heap, A complete binary tree where each node value is greater than or equal to it’s child node.  For example the below figure (left side is min heap and right side is max heap binary tree).

max heap and min heapmax heap and min heap implementation

To implement heap (max or min ) we need storage for binary heap. An array or linked list data structure can be used as a storage. It is easier to use array compare to linked list.

Heap Design notes

I have seen many implementation of max heap or min heap on the Internet. I feel there is a hurry to code heap. i suggest my readers that before jumping into the implementation, consider your implementation requirement first. it is good habit for software programming. Here is the list for what i would do before coding

  • choose array for storage.
  • Where will be the root index of the binary heap.

         Choose 0 based array or 1 based array, what is better?

If the heap’s root is placed at index 0, then the formulas for parent, left-child and right-child of the node at index n are respectively (n-1)/2, 2n+1 and 2n+2. If you use a 1-based array then the formulas become the simpler n/2, 2n and 2n + 1. So parent and left-child are more efficient when using a 1-based array. If p points to a 0-based array and q = p – 1 then we can access p[0] as q[1] so there is no overhead in using a 1-based array. ( Ref: http://stackoverflow.com/questions/6531543/efficient-implementation-of-binary-heaps ).

  • Operation to perform on the heap. ( Push(int a) , pop(),heapyfy() ).

Based on above requirement let us code the min heap.

Read next discussion c program for min heap