我有一个长度为n的数组。我想对数组元素进行排序，使我的新数组元素像
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]
等等...
我尝试过的，使用向量。
#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;
}
因此，对于长度为11的数组，我希望
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]
我的问题是，myfunc的函数定义应该是什么，以便获得预期的输出
bool myfunc (int l, int r)
{
int m = (l+r)/2;
//Cant figure out this logic
}
我已经尝试过调试器，但这绝对对定义函数没有帮助！任何线索将不胜感激。
最佳答案
似乎您希望以数组形式存储二叉搜索树（BST），并使用通常用于存储堆的相同内部表示法。
预期的输出是一个数组，使得基于一个的索引形成一棵树，对于任何基于一个索引的x，x的左节点位于索引2 * x，x的右节点位于索引2 * x + 1。此外，没有间隙，这意味着将使用数组的每个成员（最多N个）。（这是一个完整的二叉树）由于c ++使用基于零的索引，因此使用此基于一的索引时要格外小心。
这种表示树的方式对于存储堆数据结构非常有用，但是对于想要插入事物的二叉搜索树则非常不利，从而破坏了完整性，并迫使您进行非常昂贵的重新平衡。
您要求从已排序的数组索引到此数组格式的映射。我们可以使用递归函数来构建它。此递归函数将花费与构建二叉树完全相同的工作量，并且实际上，它与编写该函数的方式几乎相同，因此这不是最佳方法。我们正在做整个问题所需的工作，只是想出一个中间步骤。
这里特别需要注意的是，我们不需要中位数。我们要确保左子树形成一个完美的二叉树，以使其无间隙地适合数组。因此，它的幂必须为2，减去1个节点。正确的子树可能只是完整的。
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);
}
}
这给了我{7，3，9，1，5，8，8，10，0，2，4，6}作为索引映射。它与您的有所不同，因为您在树的左下角留有空格，并且我确保数组已完全填充，所以我不得不将最下面的行移开，然后BST属性需要重新排列所有内容。
附带说明，为了使用此映射，您首先必须对数据进行排序，这与整个问题的复杂度也差不多。
此外，使用std :: binary_search http://en.cppreference.com/w/cpp/algorithm/binary_search，排序后的向量已经为您提供了一种进行二进制搜索的高级方法。