Build max heap in which all the nodes at certain level are less than all the nodes at the level before them
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.