Skip to main content
1 of 2
Rinkesh P
  • 1k
  • 1
  • 6
  • 17

If you have $7$ (or rather $2^{n}-1$) arbitrary numbers, then brute force is the way to go. However, there are some observations if you construct a heap with all distinct numbers in the range $1 ... 2^{n}-1$.

Intuitively(for the lack of a rigorous mathematical proof), a min heap formed by inserting in reverse postorder or converse preorder traversal of the numbers $1 ... 2^{n}-1$ sorted in ascending order should give the maximum number of inversions. Example

min heap constructed using converse preorder from a sorted sequence

It is easy to see that at every level, the rightmost element, will not have inversions. For the remaining elements, visually, the inversions would look something like this

min heap inversions

i.e. every element is paired up all elements of remaining subtrees of height $h-i$ for a heap having height $h$ and a level $i$. From here an expression for the no. of inversions can be derived. We simply sum up the inversions at each level, for all levels. $$no\;of\;elements\;at\;level\;i = no\;of\;subtrees\;of\;height\;h-i = 2^{i}$$ $$no\;of\;elements\;in\;a\;complete\;binary\;tree\;of\;height\;h = 2^{h+1}-1$$ $$no\;of\;inversions\;at\;level\;i = (2^{h-i+1}-1)*\sum_{k=1}^{2^{i}-1}k$$ $$total\;no\;of\;inversions = \sum_{i=1}^{h}(2^{h-i+1}-1)*\sum_{k=1}^{2^{i}-1}k$$

Further simplification of the expression can be done, i'd say this form preserves the "meaning" of the expression in a way.

Substituting $h=2$, we get $9$ as the no. of inversions for heap having elements $1...7$, which can be verified by counting the number of inversion(coloured links except black) in the picture above.

Rinkesh P
  • 1k
  • 1
  • 6
  • 17