Last Updated: 10 Dec, 2020
Build Heap
Moderate
Asked in companies
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.
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
Approaches
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.