Build Heap

Moderate
0/80
Average time to solve is 30m
profile
Contributed by
30 upvotes
Asked in companies
OYOSamsungSAP Labs

Problem statement

You are given an integer array with N elements. Your task is to build a max binary heap from the array.

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

Note : 
You do not need to print anything, just return the vector representation of the heap such that the input array follows 0 - based indexing and :

The left child of the ith node is at (2 * i + 1)th index.

The right child of the ith node is at (2 * i + 2)th index.

Parent of the node present at ith index is at (i - 1) / 2 indexes.
Detailed explanation ( Input/output format, Notes, Images )
Input Format: 
The first line of input contains a single integer T, representing the number of test cases or queries to be run. 

Then the T test cases follow.

The first line of each test case contains the size of the array that is N.

The second line of each test case contains N space-separated integers representing the elements of the array.
Output Format: 
For each test case, if the array returned by the function buildHeap is representing a max-heap, print ‘1’ else print ‘0’.

The output of each test case is printed in a separate line.
Constraints : 
1 <= T <= 10
1 <= N <= 10^4
-10^9 <= data <= 10^9
Sample Input 1:
1
5
4 10 3 5 1
Sample Output 1:
1
Explanation For Sample Input 1:
One possible max-heap representation of array  =     10 5 3 4 1

example

Sample Input 2:
1
11
1 3 5 4 6 13 10 9 8 15 17
Sample Output 2:
1
Hint

Arrange the elements of the array starting from last such that the array should be representing heap.

Approaches (1)
Top - Down approach

The idea is to follow a top-down approach. The given array, represents a binary tree but does not follow the property of heap, in order to convert the input array to heap array heapify the complete binary tree formed from array in reverse level order following a top-down approach. It can be observed that leaf nodes need not be heapified as they already follow the heap property. Also, the array representation of the complete binary tree contains the level order traversal of the tree.

 

So find the position of the last non leaf node and perform the heapify operation of each non-leaf node in reverse level order.

 

Algorithm:

 

  • Find the last non-leaf node
    • Last non-leaf node = parent of the last node.
    • That is the parent of the node at (n - 1)th index.
    • That is the node at ((n - 1) - 1) / 2 = (n / 2) - 1  index.
  • Heapify function :
    • Let the value present at the current index be the largest.
    • Now compare its value with its left and right child if its smaller than any of them then swap their values and call heapify again for the new position of the current node.
    • Else return.
  • Do heapification for all the indices starting from the last non-leaf node to the root node.
Time Complexity

O(N * log(N)), Where N is the number of elements in the array.

 

The algorithm uses heapification which is a logarithmic algorithm and thus takes log(N) time and heapification is done for all the elements of the array, so the total time complexity will be O(N*log(N)).

Space Complexity

O(1)

 

Constant extra space is required.

Code Solution
(100% EXP penalty)
Build Heap
Full screen
Console