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

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?

• By brute-force: generate all permutations of the integers from 1 to 7, discard those that violate the heap condition and count the inversions.
– user16034
Apr 30 at 15:09
• (I think it's possible to construct such - too lazy to try and prove.) Apr 30 at 21:08

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.

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