Build Min Heap — Asked in Adobe Interview

Problem Statement :

You are given an array ‘ARR’ of integers having ’N’ elements. Your task is to convert the input array into a min-Binary Heap.

A min-Binary heap is a complete binary tree in which the value of each internal node is smaller than or equal to the values of the children of that node.

The first line of each test case contains an integer ’N’, denoting the number of elements in the array ‘ARR’.

The second line of each test case contains ’N’ space-separated integers denoting the array elements.

For each test case, the checker will print 1 if the returned array represents a valid min-heap. Otherwise, the checker will print 0.

Sample Input:

5
1 3 5 4 6

Sample Output:

1

Explanation of Sample Test Case:

One possible min-heap representation of the input array is the array [ 1, 3, 5, 4, 6 ] which is the same as the input array.

Approach :

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.

Time Complexity : O(N)
Space Complexity : O(log N)

Code :

Thanks for Reading

Placewit grows the best engineers by providing an interactive classroom experience and by helping them develop their skills and get placed in amazing companies.

Learn more at Placewit. Follow us on Instagram and Facebook for daily learning.