Building a tree with the heap property from an array and preserving its order
An O(n)-time algorithm for the problem has been published by Gabow et al. (1984) in the context of &quot;Cartesian trees&quot;: https://dl.acm.org/doi/10.1145/800057.808675
As pointed out above by Raphael, there is a close relationship to treaps.
You may also want to visit the corresponding Wikipedia entry: https://en.wikipedia.org/wiki/Cartesian_tree