Build Min Heap

The idea is to follow a top-down approach. The given array does not necessarily represent a heap. In order to convert the input array to a heap, we will heapify the complete binary tree formed from the array in reverse order, i.e., from the rightmost element to the leftmost element. Heapify is defined as the process of converting a binary tree into a Heap data structure. We do not need to heapify the leaf nodes as they are already heapified because they do not have any left child or right child. Note that the input array representation of the complete binary tree denotes the level order traversal of the tree. We need to find the position of the first non-leaf node from the right and perform the heapify operation of each node in reverse of the level order.

Heapify is the process of converting a binary tree into a Heap data structure. The heapify algorithm is a recursive algorithm that is used to heapify a node assuming that both the subtrees of the node are already heapified. In each step of heapification, we check whether the current node has a value smaller than both of its children ( if they exist ). If yes, then the node and the nodes in its corresponding subtree are already heapified. Otherwise, we swap the node with the child having a smaller value and call the heapify function recursively for that child as the subtree was changed, and now we will have to heapify it again. The recursive algorithm stops if the subtree is already heapified.

Algorithm

• Set firstNonLeaf to ( N / 2 - 1 ). We are setting the index of the first non-leaf node as ( N / 2 - 1 ). Because in a complete binary tree having N nodes, the number of leaf nodes in it are ( N + 1) / 2, and all the leaf nodes are situated at rightmost positions in its level order traversal. We have already seen that it is not required to heapify leaf nodes, so we can directly move to the first non-leaf node.
• Iterate from i = firstNonLeaf to 0.
  • Call heapify function for the i'th node of the array.
    • Define a variable smallestNode to store the index of the node having the smallest value among the current node and the left and the right child of the current node. Initialize it as i. 
    • Define the leftChild index as 2*i + 1 and the rightChild index as 2*i + 2. 
    • If leftChild is less than N and arr[leftChild] is smaller than arr[smallestNode], then update smallestNode to leftChild. In this step, we are checking if the current node's left children, if it exists, has a value smaller than its parent node and updating the smallestNode value accordingly.
    • If rightChild is less than N and arr[rightChild] is smaller than arr[smallestNode], then update smallestNode to rightChild. In this step, we are checking if the current node's right children, if it exists, has a value smaller than its parent node and updating the smallestNode value accordingly.
    • If smallestNode is not equal to i, then we will swap arr[smallestNode] with arr[i] and call the heapify algorithm for smallestNode. We are calling heapify here because when we are swapping the two values, then there may be a possibility that the updated subtree is not heapified. Hence, we need to heapify it again.
• Return the modified input array.

O(N), where ‘N’ is the number of elements in the array.

A heap of size N has at most ceil ( N / 2^(h+1) ) nodes with height h. The heapify algorithm for a node takes time proportional to its height in the worst case. The total number of iterations to heapify each node will be the summation of ( ceil ( N /  2^(h+1) ) * h ) over all values of h ( i.e. from 0 to log(N) ), which turns out to be 2*N. Hence, the overall Time Complexity will be O(N).

O(log(N)), where ‘N’ is the number of elements in the array.

In the worst case, when the input array is a max-heap. The recursion depth will be equal to the complete binary tree’s height, i.e., log(N). Hence, the overall Space Complexity will be O(log(N)).