Binary Heap

Binary heap is used to implement Priority queue. It is an array object, visualized as an almost complete binary tree.

Binary heap comes in two flavours

• Max-Heap
• Min-Heap

A max-heap is an almost complete binary tree, where, value at each node is greater than the value of its children.

Similarly, a min-heap is an almost complete binary tree where value at a node is less than both its children (unless it is a leaf node and does not have any children).

Below picture gives an example of max and min heap, and how they are actually stored in an array:

If you don't understand the relation between the tree and array, please read my previous article here...

Following are some Important points to Node about Binary Heap.

• Logically, A Binary-Heap is a Tree, but Physically it is stored in an Array. 
• An array sorted in decreasing order is a Max-Heap. Take any such array and try to represent it in the form of a tree, it will satisfy all properties of Max-heap.
• {5 14 10 27 17 11 } is a Min-Heap. (Try and draw the corresponding tree).
• The largest element in a Max-Heap is always present at the root of the tree. Second largest will be at distance 1 from root and so on.
• Number of leaf elements in the heap of size n = Ceiling of (n/2). if there are 3 nodes then 2 of them will be leaf. If there are 4 nodes then also there will be 2 leaf nodes.
• All paths from root to leaf in a Max-Heap are in nonincreasing order and Left and right sub-trees are unrelated

Heapify operation

This is an important operation in the implementation of Binary heap.

Given a max-heap (in the form of Array). A node r in the heap which violate the heap property, as shown below.

Note that all the children of Node '4' are following the heap property, Its only the root of this sub-tree where the violation is. If such is the case then heapify operation can fix it and restore the heap property of the subtree. The procedure of heapify is:

1. Compare the below 3 and find the maximum value:
    a. Value at root node
    b. Value of left child
    c. Value of Right child
2.If value at root is not maximum then swap root with the maximum value.
3. Run Heapify for the child whose value was swapped in step-2.

Let us see it in picture, Have a look at the actual changes that take place in the array (shown on the bottom right of each picture):

1. Find maximum of root (4) and its two children

2. Swap root of subtree with max value

3. Repeat the same for subtree whose root was swapped

After the heapify operation the array is a valid max-heap

Below is the code of Heapify

void heapify(int *arr, int n, int root)
{
	(root <= n/2)		// Leaf nodes are already heapified
	{
		int max=root, lptr=2*root + 1, rptr=2*root + 2;
		if(lptrarr[max])
			max = lptr;	// LEFT Child is Max
		if(rptrarr[max])
			max = rptr;	// RIGHT Child is Max
		if(max != root)
		{
			swap(&arr[root], &arr[max]);
			heapify(arr, n, max);
		}
	}
}

Time taken by the above algorithm is O(lg(n)), because we are doing constant amount of work at each level and can be at most O(lg(n)) levels.

In best case the the time taken can be O(1) when root is already maximum of there are no children of the node under consideration.

Extra memory will be taken since we are using recursion.

Build Heap Operation

This operation takes any random array as input and converts it into a heap. The heap is built in a bottom-up manner.

We start from the last element. Since the leaf nodes does not require any action, we skip all the leaf nodes and start from the first non-leaf node from the end and work backward.

As we saw above and in Almost complete Binary tree, that there in a heap of n integers half will be leaf nodes (actually ceiling of (n/2)).  So we start from index n/2 downto index zero and call the heapify operation for each node. Code:

void buildHeap(int *arr, int n)
{
   int i=0;
   for(i=n/2; i>=0; i--)
      heapify(arr, n, i);
}