Partially sorted Max Heap

Question

I need to convert a Max Heap to a "Partially Sorted Max Heap" such that all keys at depth i are smaller than all keys at depth i-1. What is the most efficient way of doing this? Can this be done in O(n)?

Answer 1

Let $H$ be the max-heap represented as an array. We assume that the elements of the heap occupy the non-zero indices of $H$ e.g. the maximum element is at index 1. Also, I will use depth instead of level but that should not be a problem.

Notice that all elements at depth $d$ of the heap and their children, which are the elements at depth $d+1$, form a contiguous subarray, $H[2^{d}], ,..., H[2^{d+2}-1]$. Call this subarray $H_d$.

Algorithm

For $d = 0$ to $ (\log n) - 1$, repeat the following:

1. Find the element that must be placed at index $j = 2^{d+1}-1$ when $H_d$ is in reversed sorted order. Call this element $m_j$. Since the elements at depth $d$ occupies the indices from $2^d$ to $2^{d+1}-1$, this element must be the minimum element among the elements at depth $d$ if $H_d$ is reversed sorted.
2. Reverse partition $H_d$ around $m_j$. That is, all elements greater than $m_j$ must be placed on its left and those that are less must be on its right.

Analysis

As noted above, $m_j$ is the minimum element among the elements at depth $d$. Hence, after each reverse partition, it is guaranteed that all elements at the left-side of $m_j$ are those that will be on depth $d$, and they are greater than those on the right-side, which will be the elements at depth $d + 1$. This satisfies the partially sorted property while also maintaining the max-heap order. Since this process is applied from top to bottom, the entire heap is transformed.

As for the running time, the selection of $m_j$ can be performed in time proportional to the size of the subarray $H_d$ using the linear time deterministic selection algorithm. The size of $H_d$ is at most $2^d + 2^{d+1} = 3\times2^{d}$. Summing up the cost for each $d$ gives

$$3*\sum_{d=0}^{(\log n) -1}2^{d}= 3(2^0 + 2^1 + ... + 2^{\log n/2}) = O(n)$$

As for the partition step, this can also be performed in time proportional to the size of $H_d$. Therefore, the total time of all the partitions is also $O(n)$. Which means that the entire algorithm takes $O(n)$ time.

Note

I feel that using the linear time selection algorithm is kind of an overkill, but I cannot find a simpler method to find $m_j$. But, overall the algorithm shows that in theory the problem can be solved in $O(n)$ time.

Answer 2

I came across a simple solution: Ignore the fact that it is a heap, reverse pardition around the median, and repeat this log(n) times, each time for the left half of the previos part...