If a given heap has $k$ inversions, what is the complexity of making it into a valid min heap? We could define an inversion as a tuple (node, descendant), where the node has a key value strictly higher than its descendant (all nodes have distinct key values).
This isn't an interview question, but is something that I thought of while learning about heaps. Searching for it on google gives zero hits.
Back when we learnt arrays and how to sort them, we were told that sorting arrays requires $\mathcal{O}(n + k)$ ($k$ = number of inversions) time complexity in insertion sort. I wonder if something similar exists for making a heap out of a given array.
I attempted to approach this problem in the following way. Assume a full binary tree (one with number of nodes equal to $2^h - 1$ ($h$ = height)). Note that we perform the sift down operation only when there exists an inversion. In the best case, the input array is already sorted so complexity is just order $n$, no sift downs are performed. In the worst case, input array is reverse sorted, so each internal node needs to be sifted down. That's summation of $\frac {(n + 1)}4 + \frac {(n + 1)}8\cdot2+\frac {(n + 1)}{16}\cdot3+\ldots= n-1$ siftdowns (solving it as a arithmetico geometric sequence) in the worst case, plus having to loop through the entire array .
In a more general case, I would say that we are visiting each node internal node once, performing a comparison with its children for cost $c$, and if it is out of place, perform a siftdown for additional cost $d$. If $i$-th internal node undergoes siftdown $k_i$ times, then we can formulate the total complexity as:
$$=\sum_{i=1}^{(n + 1) / 2}(c\cdot(k_i+1) +d\cdot k_i)$$
(as you always perform comparisons one more time than total number of siftdowns, except when you reach leaf node, which I approximated away)
This gives us:
$$=(c+d)k+\frac{(n+1)}2\cdot c$$
This suggests to me that that in worst case reverse sorted array, the order should be $n^2$, as the number of inversions $k$ is of that order. However, that we already know is not the case. Where is my analysis going wrong then?