Let's note down the facts first.
- The smallest element will be on the least level.
- The second smallest element will be on the first level.
- The third smallest element can be on the second or third level.
Root is fixed, the idea is to divide the building process into two subproblems, each solving both subtrees of the root.
Recurrence equation: T(n) = $_{k}^{n-1}\textrm{C}$ x T(k) x T(n-k-1), where k is number of nodes in left sub tree.
T(1) = 1
T(2) = 1, one root and one child.
T(3) = $_{1}^{2}\textrm{C}$ x T(1) x T(1) = 2
T(4) = $_{2}^{3}\textrm{C}$ x T(2) x T(1) = 3
T(5) = $_{3}^{4}\textrm{C}$ x T(3) x T(1) = 8
T(6) = $_{3}^{5}\textrm{C}$ x T(3) x T(2) = 20
T(7) = $_{3}^{6}\textrm{C}$ x T(3) x T(3) = 80
To put it down simply, Among 7 elements, least element is fixed as root.
We are now left with 6 elements, the left subtree will have 3 elements, which can be picked in
$_{3}^{6}\textrm{C}$ x 2 ways.
Now we have 3 elements remaining and we can complete the heap in 2 ways only.
Hence $_{3}^{6}\textrm{C}$ x 2 x 2 = 80.