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. 


Find the median in $O(n)$ using quickselect. 
Partition into two halves (greater and lesser-equal).
Insert the lesser-equal half all as leaf nodes (deepest empty nodes).
Repeat 1-3 on the greater half until you only have 1 value left which will be the max value.


Time complexity is: $$T(n) = T\left(\frac{n}{2}\right) + \Theta(n)$$
Which overall is linear $O(n)$ time complexity.