Complexity of forming a min heap out of a given array with k inversions
We remove the inversions by beginning from the bottom (furthest level from the root) and going breadth-first up.


Start at the bottom level.  We have a set of leaves, each satisfying the heap property.
Move one level up. If there is an inversion at this level, we fix it by sifting down. Now all sub-heaps from the bottom up to and including this level satisfy the heap property.
Continue applying 2. until finishing at the root level.


Suppose in the worst case that the $k$ inversions fill the top levels of a heap of height $h = \lfloor log(n) \rfloor + 1$. We have at most $\Sigma^{\lfloor log(k) \rfloor + 1}_{i = 0} 2^i \cdot (h - (i + 1))$ swaps for sifting down, where $2^i$ represents the number of inversions at a given depth from the root. This is $O(n)$.