Convert a maximum heap to a binary search tree

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

c algorithm heap binary-tree

Edit Report

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 h

answered 2011-02-11T14:22:09.697

Convert a maximum heap to a binary search tree

1 Answer

Your Answer