# Partially sorted Max Heap

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)?

• Please edit your question to define what a "Partially Sorted Max Heap" is, precisely. What have you tried? What are your thoughts? Where are you stuck? What is the most efficient way you've been able to find so far? Are you familiar with the MakeHeap/BuildHeap procedure for heaps? e.g., stackoverflow.com/q/9755721/781723
– D.W.
Jan 27 at 23:32

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.

• Thanks for the answer. A small issue: Take the array {100,20,50,10,11,30,40} which form a max-heap. When applying the partition around 20, which is the smallest at depth 1, 30 can replace it instead of 40. This seems to create a problem. Right? Or am I missing something? Thanks. – Avi Tal 14 mins ago Delete Jan 28 at 16:01
• Sorry... fixed my comment. So after d = 0, what do we get? Can we get {100,50,20,10,11,30,40}? Thanks Jan 28 at 16:04
• I made a small update in the algorithm. Let me use your example to show how it works. For $d=1$, we have $H_1= [20,50,10,11,30,40]$, because it should include everything from index $2^1=2$ to $2^3-1=7$. Now $j = 3$,so you need to find the element in $H_1$ that will be on index 3 when $H_d$ is reversed sorted, and that will 40. Partitioning around 40 will result to $[50,40,10,11,30,20]$ Jan 28 at 16:11
• Thanks!. It's starting to make sense! So you mean the process shoud not be stopped until the whole heap is "sorted", right? Otherwise for d=0... {100,20,50,...} can become {100,50,20...}. Am I correct? Jan 28 at 16:27
• Hi, appearently I found a counter example... If the leftmost path of the heap includes very large numbers, and the rest are smaller than all of the numbers on the leftmost path, this will not work. I came across a correct algorithm: Ignore the fact that it is a heap, reverse pardition around the median, and repeat this log(n) times for the left halves of the array... Feb 28 at 14:22

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