Convert Min Heap To Max Heap
You are given an array of size ‘n’ which is an array representation of min-heap. You need to convert this min-heap array representation to a max-heap array representation.
For Example- Corresponding to given min heap :-[1,2,3,6,7,8]
It can be converted to the following max heap:[8,7,3,6,2,1]
Input Format:
The first line of input contains an integer ‘T’ denoting the number of test cases.
The next 2*T lines represent test cases.
The first line contains a single integer ‘n’ denoting the size of the array.
The next line contains ‘n’ space-separated integers denoting the min-heap.
Output Format
There can be many possible max-heaps. Return any possible max-heap for given input min-heap.
Output for each query is printed in a separate line.
Note
The output max-heap will be checked from the given function:-
If the output array is max-heap it will return true else it will return false.
Constraints:
1 <= ’T' <= 10
1 <= ’n’ <= 5000
1 <= arr[ i ] <= 10^5
where 'T' denotes the number of test cases, 'n' denotes the size of the array and arr[i] denotes the elements of the input array.
Time Limit : 1 sec
CodingNinjas
author
2y
Simply build Max Heap without caring about the input. Start from the bottom-most and rightmost internal node of min Heap and heapify all internal nodes in the bottom-up way to build the Max heap.
Time ...read more
CodingNinjas
author
2y
Sorting Approach
The main idea is that when an array is sorted in descending order it becomes max heap as for every ‘i’ from i=0 to n/2 it is greater than equal to arr[2*i+1] and arr[2*i+2].
Space Compl...read moreCodingNinjas
author
2y
Heapify Approach
The main idea is to build max-heap for the given input array just like in heapsort. It will convert the input array into a max heap. We will perform the heapify(Refer Heap Sort Algorit...read more
Add answer anonymously...
Top UBS Business Technology Analyst interview questions & answers
Popular interview questions of Business Technology Analyst
Top HR questions asked in UBS Business Technology Analyst
Stay ahead in your career. Get AmbitionBox app
Helping over 1 Crore job seekers every month in choosing their right fit company
65 L+
Reviews
4 L+
Interviews
4 Cr+
Salaries
1 Cr+
Users/Month
Contribute to help millions
Get AmbitionBox app