What is the maximum inverse pairs will I have when I build a heap?

Question

Suppose that I have 7 different integers stored in an array. Among those arrange- ments that can be viewed as a min heap, what is the maximum number of inverse pairs within the array?

Answer 1

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

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

i.e. every element is paired up with 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 inversions(coloured links except black) in the picture above.

Answer 2

By exhaustive search, $[1, 5, 2, 7, 6, 4, 3]$ has $9$ inversions.