2

这个问题类似于完成 BST 数组表示的排序列表，但可能更具体。这个问题可以用来解决在 Complete Binary Search 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)接受一个未排序的数组（可以看作是一个未排序的完整二叉树）并排列它的元素（可以看作是树的旋转）以将树变成一个完整的二叉堆，其中每个节点的值都大于它的任何一个子节点。我们说结果数组是“最大堆顺序”。

另一方面，如果每个节点的值都大于其左孩子但小于其右孩子，那么我们说完全二叉树是完全二叉搜索树。在这种情况下，假设结果数组处于“级别顺序”。[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

我正在寻找的是一系列有效的算法：

  1. 将未排序的序列排列成水平顺序
  2. 将已排序的序列排列为级别顺序
  3. 将级别顺序序列排列为排序顺序

当我说高效时，我的意思是无需深度递归、无需动态内存分配且无需临时数组即可工作的算法。我已经知道置换不能特别快地完成；我希望 O(n lg n)。

请注意，第 2 部分和第 3 部分基本上要求提供映射OldIndex -> NewIndex；一旦有了这样的功能，您就可以使用其中一种算法就地进行排列。

第 1 部分要求nonstd::make_searchtree通过类比来实现std::make_heap. 第 3 部分要求nonstd::sort_searchtree通过类比来实现std::sort_heap.

[1]——我基本上是编造了“水平顺序”这个词。如果您知道此排序的更广泛认可的学术术语，请发表评论！

4

1 回答 1

2

我们可以得到 1 的 Theta(n log n) 时间算法和 2 和 3 的线性时间算法，如下所示。对于 1，我们排序并应用 2。对于 2，我们使用反向Faro shuffle和旋转使叶子到达数组的末尾，然后在去掉叶子的子树。对于 3，我们以相反的顺序执行 2 的逆步骤。

下面的 C++ 代码使用 Theta(n log n) Faro shuffle/inverse shuffle 算法，因为它比Peiyush Jain 的算法更容易。请注意，对于任何实际的 n 值，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);
}
于 2019-02-17T22:15:23.630 回答