How to map array elements to select binary tree nodes?

Question

I have an array of length n. I want to sort the array elements such that my new array elements are like

arr[0] = arr[n/2]
arr[1] = arr[n/4]
arr[2] = arr[3n/4]
arr[3] = arr[n/8]
arr[4] = arr[3n/8]
arr[5] = arr[5n/8] 

and so on...

What I have tried, using vectors.

#include <iostream>
#include <algorithm>
#include <vector>

bool myfunc (int l, int r)
{
        int m = (l+r)/2;
        return m;
}

int main()
{
    std::vector<int> myvector = {3,1,20,9,7,5,6,22,17,14,4};
    std::sort (myvector.begin(), myvector.end(), myfunc);

    for (std::vector<int>::iterator it=myvector.begin(); it!=myvector.end(); ++it)
        std::cout << ' ' << *it;
    std::cout << '\n';

    return 0;

}

So, for an array for length 11, I expect

myvector[0] = arr[5]
myvector[1] = arr[2]
myvector[2] = arr[8]
myvector[3] = arr[0]
myvector[4] = arr[3]
myvector[5] = arr[6]
myvector[6] = arr[9]
myvector[7] = arr[1]
myvector[8] = arr[4]
myvector[9] = arr[7]
myvector[10] = arr[10]

My question is, what should be my function definition of myfunc, such that I get expected output

bool myfunc (int l, int r)
    {
            int m = (l+r)/2;
            //Cant figure out this logic
    }

I have tried debugger, but that definitely doesnt help in defining the function! Any clues would be appreciated.

Answer 1

It appears you want a binary search tree (BST) stored in array form, using the same internal represenation which is often used to store a heap.

The expected output is an array such that the one based indexes form a tree, where for any one-based index x, the left node of x is at index 2*x, and the right node of x is at index 2*x+1. Additionally, there are no gaps, meaning every member of the array is used, up to N. (It is a complete binary tree) Since c++ uses zero-based indexing, you need to be careful with this one-based index.

That way of representing a tree is very good for storing a heap data structure, but very bad for a binary search tree where you want to insert things, thus breaking the completeness, and forcing you into a very expensive rebalance.

You asked for a mapping from the sorted array index to this array format. We can build it using a recursive function. This recursive function will take exactly the same amount of work as it would have taken to build the binary tree, and in fact, it is nearly identical to how you would write that function, so this is not an optimal approach. We are doing as much work as the entire problem requires, just to come up with an intermediary step.

The special note here is that we do not want the median. We want to ensure that the left subtree forms a perfect binary tree, so that it fits in the array with no gaps. Therefore, it must have a power of 2, minus 1 nodes. The right subtree can be merely complete.

int log2(int n) {
    if (n > 1)
        return 1 + log2(n / 2);
    return 0;
}

// current_position is the index in bst_indexes
void build_binary_tree_index_mapping(std::vector<int> &bst_indexes, int lower, int upper, int current_position=0) {
    if (current_position >= bst_indexes.size())
        return;

    int power = log2(upper - lower);
    int number = 1 << (power); // left subtree must be perfect
    int root = lower + number - 1;

    // fill current_position
    // std::cout << current_position << " = " << root << std::endl;
    bst_indexes[current_position] = root;

    if (lower < root) {
        // fill left subtree
        int left_node_position = (current_position + 1) * 2 - 1;
        build_binary_tree_index_mapping(bst_indexes, lower, root - 1, left_node_position);
    }

    if (root < upper) {
        // fill right subtree
        int right_node_position = (current_position + 1) * 2 + 1 - 1;
        build_binary_tree_index_mapping(bst_indexes, root + 1, upper, right_node_position);
    }
}

This gives me {7, 3, 9, 1, 5, 8, 10, 0, 2, 4, 6} as the index mapping. It differs from yours because you left spaces in the lower left of the tree, and I am ensuring that the array is completely filled, so I had to shift the bottom row over, then the BST property required reordering everything.

As a side note, in order to use this mapping, you first must sort the data, which is also about the same complexity as the whole problem.

Additionally, the sorted vector already gives you a superior way to do a binary search, using std::binary_search http://en.cppreference.com/w/cpp/algorithm/binary_search.