Convert a maximum heap to a binary search tree

Question

We are given an array of 2^m - 1 distinct, comparable elements, indexed starting from 1.

We can view the array as a complete binary tree:

Node is placed at index i.
Left child is placed at 2i.
Right child is placed at 2i+1.

For instance, the array

[7 6 4 5 2 3 1]

is the tree

       7
    /    \
   6       4
  /  \    / \
 5    2   3  1 

Now when viewed as a binary tree, these elements satisfy the heap property, a node is greater than both its children:

A[i] > A[2i] and A[i] > A[2i+1]

Are there reasonably fast, in-place algorithm to shuffle the elements of the array around so that the resulting binary tree (as described above) is a binary search tree?

Recall that in a binary search tree, a node is greater than all its left descendants, and less than all its right descendants.

For instance the reshuffle of the above array would be

[4 2 6 1 3 5 7]

which corresponds to the binary search tree

       4
    /    \
   2       6
  /  \    / \
 1    3   5  7 

Answer 1

First we note that we can -- without loss of generality -- assume that we have the elements 1,2,3,... 2^m-1 in our binary tree. So, from now on, we assume that we have these numbers.

Then, my attempt would be some function to convert a sorted array (i.e. 1 2 3 4 5) into an array representing a sorted binary tree.

In a sorted binary tree with (2^m)-1 elements we have always that the "bottom" of the tree consists of all the uneven numbers, e.g. for m=3:

     4
  2     6
 1 3   5 7

This means, in the corresponding array, we have that the last numbers are all the uneven numbers:

4 2 6 1 3 5 7
      -------
         ^
         uneven numbers!

So we can construct the last "row" of the binary tree by ensuring that the last 2^(m-1) numbers in the corresponding array are all the uneven numbers. So all we need to do for the last row is to construct a function that moves all elements at positions with uneven indices to the last row.

So let us for now assume that we have a routine that -- given a sorted array as input -- establishes the last row correctly.

Then we can call the routine for the whole array to construct the last row while all other elements stay sorted. When we apply this routine on the array 1 2 3 4 5 6 7, we have the following situation:

2 4 6 1 3 5 7
      -------
         ^
         correct!

After the first round, we apply the routine for the remaining subarray (namely 2 4 6) which constructs the second last "row" of our binary tree, while we leave the remaining elements unchanged, so we get the following:

 now correct as well!
   v
  ---
4 2 6 1 3 5 7
      -------
         ^
         correct from run before

So all we have to do is to construct a function that installs the last row (i.e. the second half of the array) correctly!

This can be done in O(n log n) where n is the input size of the array. Therefore, we just traverse the array from end to the beginning and exchange the uneven positions in such a way that the last row (i.e. the latter half of the array) is correct. This can be done in-place. Afterwards, we sort the first half of the array (using e.g. heapsort). So the whole runtime of this subroutine is O(n log n).

So the runtime for an array of size n in total is:

O(n log n) + O(n/2 log n/2) + O(n/4 log n/4) + ... which is the same as O(n log n). Note that we have to use a in-place sorting algorithm such as Heapsort so that this whole stuff works completely in-place.

I'm sorry that I can't elaborate it further, but I think you can get the idea.