Complexity of forming a min heap out of a given array with k inversions

Question

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?

Answer 1

We remove the inversions by beginning from the bottom (furthest level from the root) and going breadth-first up.

1. Start at the bottom level. We have a set of leaves, each satisfying the heap property.
2. 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.
3. 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)$.

Answer 2

First of all, note that if we take a proper min-heap and look at it as an array, it could still have many inversions. The second part of the heap-sort algorithm is to convert this type of array into a sorted one (i.e. an array with 0 inversions). For example, a node in a min-heap can be larger than its sibling and the sibling's whole sub-tree. Therefore a good question that you can work on could be that what's the maximum number of inversions in a proper min-heap (Spoiler: you will find it to be quite large!). So in the process of making a min-heap, we do not eliminate all of the inversions necessarily. We might reduce or even increase that number (Can you find an example that a siftdown increases inversions?).

The other problem in your analysis is that changing the level (depth) of a node in a heap by 1 can reduce (or increase) the number of inversions by more than 1. In fact, this can change the number of inversions in relation to the number of nodes in that level (depth).

EDIT: Looks like I've misread your question. If we consider inversions to be tuples of nodes and descendants with the descendant bigger than the node, then the root can produce $n-1$ inversions, the nodes in the next layer can have inversions with all nodes in their subtrees and each produce $(n-3)/2$ inversions and so on. Therefore the number of inversions in the whole tree would be $T(n) = 2 T(\frac{n-1}{2})+n-1$, which is $O(nlogn)$.

Answer 3

Regardless of your analysis, the time taken to create a min-heap will always be linear i.e. $O(n)$. Inversions have no effect on this worst case complexity.

Imagine if you are given a problem where you have to convert a max-heap into a min-heap. In this case the inversions will be maximum in number, but this problem can be solved in linear time regardless of inversions. Why? Because we have to restore the heap property for all nodes in the heap. The leaf nodes already follow the heap property. The only nodes that might or might not are the internal nodes.

So if we restore heap property for the internal nodes then we are done and this can be done by heapifying the internal nodes one by one starting from the second last level from the bottom which takes linear time.