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.

Answer 2

Let n = 2^m - 1. In linear time, we can both make a max-heap and extract the elements of a binary search tree in sorted order, so the best we can hope for (assuming comparison-based algorithms) is O(n log n) time and O(1) space. Here is such an algorithm.

1. For j = n down to 1, pop the max element from the j-element max-heap and store it at (newly vacated) location j. This sorts the array.

2. Convert the sorted array to a binary search tree with a divide and conquer strategy. (Naively this is Omega(log n) space, but I believe we can compress the stack to O(1) log(n)-bit words.)

   a. Treeify the elements less than the root.

   b. Treeify the elements greater than the root.

   c. Merge the trees by rotating the leaves less than the root into position (= three reverses) so as to leave a subproblem of half the size (O(n)).

   (08 04 12 02 06 10 14 01 03 05 07 09 11 13 15)16(24 20 28 18 22 26 30 17 19 21 23 25 27 29 31)

   (08 04 12 02 06 10 14)16(24 20 28 18 22 26 30)01 03 05 07 09 11 13 15 17 19 21 23 25 27 29 31

   (08 04 12)16(24 20 28)02 06 10 14 18 22 26 30 01 03 05 07 09 11 13 15 17 19 21 23 25 27 29 31

   (08)16(24)04 12 20 28 02 06 10 14 18 22 26 30 01 03 05 07 09 11 13 15 17 19 21 23 25 27 29 31

   16 08 24 04 12 20 28 02 06 10 14 18 22 26 30 01 03 05 07 09 11 13 15 17 19 21 23 25 27 29 31

Answer 3

Just some basic ideas:

1. A binary search tree is a binary tree.
2. Both children of the root are either nil or themselves binary search trees
3. The values satisfy the following condition: left child < root < right child

Condition 1 is not problem - the heap is a binary tree as well. Condition 2 is problematic but suggests a bottom up approach. Condition 3 is not satisfied as well.

Bottom up means: - We start with all leaves - this is unproblematic, they are binary search trees. - Now we continue with a recursive walk through each level of parents up to the root. - Swap the subtrees if the left child is larger than the right child. - Swap the root with the larger value of the 2 children (it's the right child) - This might not be enough - you might need to continue to correct the right subtree until it is a binary search tree again.

This should work. But still - removing the top element and inserting it into a self balancing tree will be the faster/better approach and a lot easier to implement (e.g. using standard components like std::map in c++).

Another idea: for binary search trees holds the property that a left-root-right walk through the tree obtains the sorted values. This could be done reverse. Getting the values sorted from the heap should be easy as well. Just try to combine this - reading from the heap and writing the tree directly from the sorted values. This can be done in O(n) I think - but I'm not sure wether it can be done in place or not - I guess not.