Building a tree with the heap property from an array and preserving its order How efficiently can I build a binary tree satisfying the heap property from an array and such that the inorder traversal of the tree is the original array?

For example, if I have:


  2 1 5 6 2 3


I want to build:

  1
 / \
2   2
   / \
  5   3
   \
    6


Because it has the heap property and its inorder is the original array 2 1 5 6 2 3.
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