Skip to main content
added 6 characters in body
Source Link
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 inversionsmin 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 inversioninversions(coloured links except black) in the picture above.

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.

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.

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