Q120: Optimal way to build a heap?

Posted on by bytesoftheday

Question #120: How much time will it take to build a min heap using an optimal solution?

Options:

  1. O(n log(n) )
  2. O(n)
  3. O(n2)
  4. O(log(n))

Solution: There are multiple ways to build a heap. First is – we insert element one by one. Insertion in a heap take log(n) steps, and if we insert ‘n’ elements one by one, it becomes O(n log(n)). The other technique is – just build a complete binary tree first of the elements in any order. Then, starting from the nodes at last level, traverse upwards and heapify that node by placing it to the appropriate position in the heap formed till now. For example, if we have elements in the following order:

23, 19, 2, 12, 31, 4, 3, 7, 20

Then as the first step, we can just build a complete binary tree by inserting elements as follows:

build_heap_1

 

The leaf nodes 7 and 20 are trivially a heap. Going upwards, we need to heapify 12 and place it at the correct position. Since we are forming a min-heap, 12 would be replaced by the smaller of its two children, hence the next step modifies the heap as follows:

build_heap_2

Similarly, nodes 31, 4 and 3 are trivially a heap. Going upwards one more step, 19 would be placed at the correct position and can traverse till the leaf node. The next step modifies the heap as follows:

build_heap_3

This can be continued till the root node. And the final heap that will be formed will look like following:

build_heap_4

The complexity to build a heap using this technique would be O(n). Hence, the correct answer is option 2.