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?

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

2 Answers 2


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 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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.