Build Heap
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

Question

Build Heap

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

Accepted Answer

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.

Space Complexity: O(1)Explanation:

O(1)

Constant extra space is required.

Time Complexity: O(nlogn)Explanation:

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)).

Java (SE 1.8)

/*

	Time complexity: O(N * (log(N))) 

	Space complexity: O(1)

	

	where N is the total number of elements in the array.

*/



import java.util.ArrayList;



public class Solution 

{

    public static void heapify(ArrayList arr, int n, int i)

    {

        

    	// Initializing largest with root

        int largest = i;



        // Left child of current node

        int left = 2 * i + 1;



        // Right child of current node

        int right = 2 * i + 2;



        // If left child is greater than the current node

        if(left < n && arr.get(left) > arr.get(largest))

        {

            

            // update largest

            largest = left;

        }



        // If right child is greater than current node

        if(right < n && arr.get(right) > arr.get(largest))

        {

            

            // update largest

            largest = right;

        }



        // If the current node is not the largest 

        if(largest != i)

        {

            

            // swap the values

            int temp = arr.get(i);

            arr.set(i, arr.get(largest));

            arr.set(largest, temp);



            // and recursively heapify the affected subtree

            heapify(arr, n, largest);

        }    

    }

    

    public static ArrayList buildHeap(ArrayList arr, int n) 

    {

        

        // The last non - leaf node

        int startIdx = (n / 2) - 1;



        // Perform reverse level order traversal from last non-leaf node and heapify each node 

        for (int i = startIdx; i >= 0; i--) 

        { 

            heapify(arr, n, i); 

        } 



        return arr;

    }

}

C++ (g++ 5.4)

/*

	Time complexity: O(N * (log(N))) 

	Space complexity: O(1)

	

	where N is the total number of elements in the array.

*/



void heapify(vector &arr, int n, int i){

	

	// Initializing largest with root

	int largest = i;

	

	// Left child of current node

	int left = 2*i + 1;

	

	// Right child of current node

	int right = 2*i + 2;

	

	// If left child is greater than the current node

	if(left < n && arr[left] > arr[largest])

    {

	

    	// update largest

		largest = left;

	}

	

	// If right child is greater than current node

	if(right < n && arr[right] > arr[largest])

    {

		

        // update largest

		largest = right;

	}

	

	// If the current node is not the largest 

	if(largest != i)

    {



		// swap the values

		int temp = arr[i];

		arr[i] = arr[largest];

		arr[largest] = temp;

		

		// and recursively heapify the affected subtree

		heapify(arr, n, largest);

	}

	

}



vector buildHeap(vector arr, int n){

	

	// The last non - leaf node

	int startIdx = (n/2) - 1;

	

	// Perform reverse level order traversal from last non-leaf node and heapify each node 

    for (int i = startIdx; i >= 0; i--) { 

        heapify(arr, n, i); 

    } 

    return arr;

}

Python (3.5)

'''

	Time complexity: O(N * (log(N)))

	Space complexity: O(1)



	where N is the total number of elements in the array.

'''



def heapify(arr, n, i):



    # Initializing largest with root

    largest = i



    # Left child of current node

    left = 2*i + 1



    # Right child of current node

    right = 2*i + 2



    # If left child is greater than the current node

    if(left < n and arr[left] > arr[largest]):



        # update largest

        largest = left



    # If right child is greater than current node

    if(right < n and arr[right] > arr[largest]):



        # update largest

        largest = right



    # If the current node is not the largest

    if(largest != i):



        # swap the values

        temp = arr[i]

        arr[i] = arr[largest]

        arr[largest] = temp



        # and recursively heapify the affected subtree

        heapify(arr, n, largest)





def buildHeap(arr, n):



    # The last non - leaf node

    startIdx = (n // 2) - 1



    # Perform reverse level order traversal from last non-leaf node and heapify each node

    for i in range(startIdx, -1, -1):

        heapify(arr, n, i)



    return arr