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.

--

--

--

Upskilling students for tech placements!

Love podcasts or audiobooks? Learn on the go with our new app.

Recommended from Medium

UNDERGRAD DIARIES: TimberFever 2018

Docker + Rails + React + Selenium = 🔥

ALQO Masternode Guide

Achieving Remote Code Execution via Unrestricted File Upload

[Leetcode] Jump Game

WEEEK Week #35: Filters on iOS and Voice tasks on Android

Enabling a subscription model in IT Service Delivery

My Journey @Appsecco

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store
Placewit

Placewit

Upskilling students for tech placements!

More from Medium

Course Schedule ( Leetcode 207)

Leetcode Solutions — 2Sums

Add Odd or Subtract Even Coding Question

Maximum Points You Can Obtain from Cards — LeetCode