# Build max heap in which all the nodes at certain level are less than all the nodes at the level before them

Max-heap is called a "strong" max-heap if all the nodes at certain level are less than all the nodes at the level before them. What is the most efficient way to build such a heap from a given array?

I was thinking about something similar to the regular build heap algorithm: scanning the array from right to left, compare every node to all of the nodes at the level below her, replace her with the max node and continuing until it reaches to the right position. However, I'm not sure How to make it more efficient. Thanks

Here's a simple way to approach it. Let's assume the array has $n = 2^k - 1$ distinct elements for convenience.
1. Find the median in $O(n)$ using quickselect.
Time complexity is: $$T(n) = T\left(\frac{n}{2}\right) + \Theta(n)$$ Which overall is linear $O(n)$ time complexity.