Problem

Submissions

Hints & solutions

Discuss

Convert Min-Heap to Max-Heap

Moderate

0/80

Average time to solve is 26m

Contributed by

15 upvotes

Asked in company

Problem statement

You are given an array/list (arr) representing a min-heap. Your task is to write a function that converts the min-heap to a max-heap.

Note :

Change in the input array/list itself. You don't need to return or print the elements.

Detailed explanation ( Input/output format, Notes, Images )

Input format :

The first line contains an integer 't' which denotes the number of test cases or queries to be run. Then the test cases follow.

The first line of each test case or query contains an integer 'N' representing the size of the array/list.

The second line contains 'N' single space separated integers representing the elements in the array/list which are in the form of a min-heap.

Output Format :

For each test case or query, If the built max-heap satisfies the max-heap condition, print 'true'. Otherwise, print 'false'(without quotes).

Output for every test case will be printed in a separate line.

Note :

You don't have to print anything, it has already been taken care. Build the max-heap in the given array/list itself or in-place

Constraints :

1 <= t <= 100
0 <= N <= 10^5

Time Limit: 1 sec

Sample Input 1 :

1
7
1 2 3 4 5 6 7

Sample Output 1 :

true

Explanation for Input 1:

For a min-heap, there can be multiple max heap. For example:

Since it is possible to create a max heap so answer should be true.

Sample Input 2 :

1
2
1 2

Sample Output 2 :

true

Explanation for Input 2 :

In this case, there is only one max heap possible.

Hint 1

Hint 2

Don't try to convert a min heap to max heap. Just collect all numbers from the min heap and construct a max heap like you would normally do

Approaches (2)

Approach 1

Approach 2

Brute Force Approach

For this approach, we will first copy the elements of the min-heap array to a soon-to-be-max-heap array using a for-loop. After copying each element to the max-heap array, we will heapify it to move it to its correct position. Following is the procedure for heapifying:

1. For every index in the heap, find its left child and right child. This can be done by calculating 2i + 1 and 2i + 2 where i is the index of the current element

2. Then find the maximum element among the left and right children and the current element.

3. If the current element is the maximum, then we will move on to the next index, otherwise, we will the swap the current element with the maximum element and recurse the heapify function on the maximum element

Time Complexity

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

Since you're creating a max heap from scratch.

Space Complexity

O(N), Where N is the size of the input array/heap.

We are using maxHeap array that takes O(N) space.

(100% EXP penalty)

Convert Min-Heap to Max-Heap

Console