这个问题类似于Sorted list to complete BST array representation，但也许更具针对性。这个问题可以用来解决Inserting node dynamically in Complete Binary Search Tree。
考虑一个complete binary tree在记忆中表示为连续数组a[0..n)，其中元素a[0]是树的根，并且对于任何节点a[i]，它已经离开了孩子a[2*i+1]和右子a[2*i+2]（如果那些指数小于n）。
C ++程序员将熟悉这种表示，因为std::make_heap使用它。 std::make_heap(a, a+n)获取一个未排序的数组（可以看作未排序的完整二叉树）并置换其元素（可以看作树旋转），将树转换为完整的二进制heap，其中每个节点的值大于其子节点。我们说结果数组是“最大堆顺序”。
另一方面，如果每个节点的值大于其左子节点但小于其右子节点，则我们说完整的二叉树是完整的二叉搜索树。在这种情况下，假设结果数组是“级别顺序”。[1]
虽然对于给定的元素集存在许多允许的“最大堆顺序”，但每组元素仅具有单个唯一的“级别顺序”。
以下向量按级别顺序排列：
std::vector<int> v1 = { 3, 1, 4, 0, 2 };
// corresponds to the complete binary search tree
// 3
// 1 4
// 0 2
std::vector<int> v2 = { 6, 3, 8, 1, 5, 7, 9, 0, 2, 4 };
// corresponds to the complete binary search tree
// 6
// 3 8
// 1 5 7 9
// 0 2 4
我正在寻找的是一系列高效算法：
当我说效率时，我的意思是算法没有深度递归，没有动态内存分配，没有临时数组。我已经知道排列不能特别快;我希望O（n lg n）。
请注意，第2部分和第3部分基本上要求提出映射OldIndex -> NewIndex;一旦你有这样的功能，你就可以使用one of these algorithms进行就地排列。
第1部分要求通过类比nonstd::make_searchtree实施std::make_heap。第3部分要求通过类比nonstd::sort_searchtree实施std::sort_heap。
[1] - 我基本上把这个术语称为“等级顺序”。如果您对此订购有更广泛认可的学术术语，请发表评论！
我们可以得到1的Theta（n log n）时间算法和2和3的线性时间算法，如下所示。对于1，我们排序并应用2.对于2，我们使用逆Faro shuffle和旋转来使叶子到数组的末尾，然后在子树上“递归”（尾部递归，因此它实际上只是一个for循环）删除了叶子。对于3，我们以相反的顺序执行2的反向步骤。
下面的C ++代码使用Theta（n log n）Faro shuffle / inverse shuffle算法，因为它比Peiyush Jain's algorithm更容易。请注意，由于其缓存利用率较低，Peiyush的算法在实际硬件上的任何实际值都可能不会更快。
我已经测试了下面的代码，实际上是一个输入。特此警告你。
#include <algorithm>
#include <cassert>
#include <iostream>
#include <iterator>
#include <numeric>
#include <vector>
namespace {
// Transforms [a0 b0 a1 b1 ... an-1 bn-1 an] to [a0 a1 ... an b0 b1 ... bn-1]
// and returns an iterator to b0. The running time is Theta(n log n). If you're
// feeling ambitious, you could try Peiyush Jain's linear-time algorithm.
template <typename RandomAccessIterator>
RandomAccessIterator InvertFaroShuffle(RandomAccessIterator first,
RandomAccessIterator last) {
using Index =
typename std::iterator_traits<RandomAccessIterator>::difference_type;
Index size = last - first;
assert((size & 1) == 1);
if (size == 1) {
return last;
}
RandomAccessIterator middle = first + (((size + 1) >> 2) << 1);
return std::rotate(InvertFaroShuffle(first, middle - 1), middle,
InvertFaroShuffle(middle, last));
}
// Theta(n log n)-time algorithm for #2.
template <typename RandomAccessIterator>
void SortedToLevelOrder(RandomAccessIterator first, RandomAccessIterator last) {
using Index =
typename std::iterator_traits<RandomAccessIterator>::difference_type;
Index size = last - first;
if (size <= 1) {
return;
}
unsigned height = 1;
while ((Index{2} << height) - 1 < size) {
height++;
}
for (unsigned level = height; level > 0; level--) {
Index effective_size = std::min((Index{2} << level) - 1, size);
Index leaf_count =
std::min(Index{1} << level, size - ((Index{1} << level) - 1));
InvertFaroShuffle(first, first + 2 * leaf_count - 1);
std::rotate(first, first + leaf_count, first + effective_size);
}
}
// Theta(n log n)-time algorithm for #1.
template <typename RandomAccessIterator>
void UnsortedToLevelOrder(RandomAccessIterator first,
RandomAccessIterator last) {
std::sort(first, last);
SortedToLevelOrder(first, last);
}
// Transforms [a0 a1 ... an b0 b1 ... bn-1] to [a0 b0 a1 b1 ... an-1 bn-1 an].
// The running time is Theta(n log n). If you're feeling ambitious, you could
// try Peiyush Jain's linear-time algorithm.
template <typename RandomAccessIterator>
void FaroShuffle(RandomAccessIterator first, RandomAccessIterator last) {
using Index =
typename std::iterator_traits<RandomAccessIterator>::difference_type;
Index size = last - first;
assert((size & 1) == 1);
if (size == 1) {
return;
}
Index half = (size + 1) >> 1;
RandomAccessIterator middle = first + half;
Index quarter = half >> 1;
middle = std::rotate(first + quarter, middle, middle + quarter);
FaroShuffle(first, middle - 1);
FaroShuffle(middle, last);
}
// Theta(n log n)-time algorithm for #3.
template <typename RandomAccessIterator>
void LevelOrderToSorted(RandomAccessIterator first, RandomAccessIterator last) {
using Index =
typename std::iterator_traits<RandomAccessIterator>::difference_type;
Index size = last - first;
if (size <= 1) {
return;
}
unsigned height = 1;
while ((Index{2} << height) - 1 < size) {
height++;
}
for (unsigned level = 1; level < height + 1; level++) {
Index effective_size = std::min((Index{2} << level) - 1, size);
Index leaf_count =
std::min(Index{1} << level, size - ((Index{1} << level) - 1));
std::rotate(first, first + (effective_size - leaf_count),
first + effective_size);
FaroShuffle(first, first + 2 * leaf_count - 1);
}
}
void PrintList(const std::vector<int>& list) {
for (int elem : list) {
std::cout << ' ' << elem;
}
std::cout << '\n';
}
} // namespace
int main() {
std::vector<int> list(10);
std::iota(list.begin(), list.end(), 0);
PrintList(list);
SortedToLevelOrder(list.begin(), list.end());
PrintList(list);
LevelOrderToSorted(list.begin(), list.end());
PrintList(list);
}