高效的数据结构用于插入操作

Question

我正在寻找一种数据结构（类似于数组），它允许在该结构中快速插入值（速度比O（N）更快）。该数据结构必须能够按照插入的方式打印出其元素，类似于List.Insert()。但是，我不需要随机访问或删除。插入总是在“数组”的大小范围内进行的。所有值都是唯一的，不需要其他操作。

例如，如果Insert（x，i）在索引i（从0开始）处插入值x，则： - Insert(1, 0) 得到 {1} - Insert(3, 1) 得到 {1,3} - Insert(2, 1) 得到 {1,2,3} - Insert(5, 0) 得到 {5,1,2,3}

并且最终需要能够打印出{5,1,2,3}。

我使用的是C ++。

- Peter

---

“array like” 是什么意思？ - juanchopanza

您对遍历数据结构的复杂度有要求吗？ - Luc Touraille

@juanchopanza 我的意思是表面上它应该像一个线性数组一样运作。它应该以我插入它们的方式保留元素。 - Peter

@LucTouraille 所以插入应该是次线性的（O(lgN)等），但输出数组内容不必非常快（O(N)或O(NlgN)都可以）。 - Peter

@juanchopanza 如果我没记错的话，std::list 在插入操作上可以达到O(1)的时间复杂度，但前提是你有目标位置的指针（迭代器）。然而，获得这个指针需要进行线性搜索。 - Peter

Answer 1

使用跳表。另一个选项应该是分层向量。跳表可以在const O(log(n))时间内执行插入操作，并保持数字有序。分层向量支持O(sqrt(n))插入，并且可以按顺序打印元素。

编辑：根据amit的评论，我将解释如何在跳表中找到第k个元素：

对于每个元素，您都有一个链接到下一个元素的塔，并且对于每个链接，您都知道它跳过了多少个元素。因此，在寻找第k个元素时，从列表的头部开始并沿着塔向下移动，直到找到跳过不超过k个元素的链接。您转到由此节点指向的节点，并将k减去您已经跳过的元素数。继续这样做，直到k = 0。

- Ivaylo Strandjev

---

我也在考虑跳表，你能否详细说明一下如何修改访问链接列表（保证O(logn)搜索）在任意位置插入元素后？这不会导致需要更改很多吗？我相信它[跳表]可以被修改以适应这里，但我认为这一点应该详细说明。 - amit

实际上，我之前实现跳表的方式是从不更改节点的高度。这依赖于一个事实，即如果您使用均匀分布的高度插入每个新节点，则元素的高度将足够接近完美高度。互联网上对此方法的摊销复杂度进行了一些分析，表明它并不比最佳方法差多少。 - Ivaylo Strandjev

我不理解的是如何修改不仅高度，还有索引，怎么知道这个元素是第k个？如果你的“键”是索引，那么每次插入都需要改变链表的整个尾部吗？（我担心的不是高度，使用非确定性链表可以很好地解决这个问题） - amit

每个元素都有一座指向下一个元素的塔，对吗？每个链接都知道跳过了多少元素。所以要查找第k个元素，你从列表的头开始向下遍历塔，直到找到一个链接跨越的元素数不超过k。然后前往一个新节点，并将k减去你已经跳过的元素数。继续这样做，直到k等于0为止。 - Ivaylo Strandjev

太好了，这解释得非常清楚。点赞！我建议将这个解释添加到答案本身中。[实际上，我现在感觉很蠢，因为这与通过向每个节点添加“numberOfSons”字段来维护BST中的索引的想法非常相似] - amit

Answer 2

你可以使用一个 std::map 映射（索引，插入时间）对应的值，其中插入时间是一个“自增”整数（在 SQL 术语中）。这些对应值的排序应该是按照：

(i, t) < (i*, t*)

iff

i < i* or t > t*

在代码中：

struct lt {
    bool operator()(std::pair<size_t, size_t> const &x,
                    std::pair<size_t, size_t> const &y)
    {
        return x.first < y.first || x.second > y.second;
    }
};

typedef std::map<std::pair<size_t, size_t>, int, lt> array_like;

void insert(array_like &a, int value, size_t i)
{
    a[std::make_pair(i, a.size())] = value;
}

- Fred Foo

---

假设我们在0处插入300，然后在0处插入100，然后在1处插入200。应该发生什么:[]然后是[300]，然后是[100 300]，最后是[100 200 300]。但实际上会发生什么呢：[]，然后是[((0, 1), 300)]，然后是[((0, 2), 100), ((0, 1), 300)]，到这里还好，但之后是[((0, 2), 100), ((0, 1), 300), ((1, 3), 200)]。结论是：如果没有顺序统计数据结构，通常很难完成这种操作。 - Evgeni Sergeev

Answer 3

默认情况下GCC包含的一种解决方案是rope数据结构。这里是文档。通常在处理长字符串时会想到绳索，但这里我们使用的是int而不是字符，但原理相同。只需将int用作模板参数。（也可以是pair等）。

这里是Wikipedia上关于绳索的描述。

基本上，它是一棵二叉树，维护左右子树中有多少元素（或等效信息，也称为顺序统计量），并且在插入和删除元素时适当地旋转子树以更新这些计数。这使得操作具有O(lg n)的时间复杂度。

- Evgeni Sergeev

Answer 4

你考虑过使用 std::map 或者 std::vector 吗？

你可以使用一个以插入顺序为键的 std::map。而 vector 有一个 reserve 成员函数。

- Basile Starynkevitch

---

OP想要比线性更快的任意插入，难道vector和map都不是O(n)吗？ - amit

是的，std::vector 在插入到位置 i 时的时间复杂度为 O(n)，因为元素 i 到 n 都需要被移动。对于 std::map，类似的情况也会发生，因为键需要被更新。 - Fred Foo

@Yavar：但是每次插入后，您将不得不修改所有后续元素的索引。假设您有map=[(1,a),(2,b),(3,c)]，并且您想在位置0添加z，则需要修改map为[(1,z),(2,a),(3,b),(4,c)]。如果有解决方法-应该进行详细说明... - amit

@juanchopanza：是的，但它强制唯一键。您需要额外的工作来允许将多个插入插入到相同的索引中而不清除先前的元素。 - Fred Foo

Answer 5

关于您的评论：

列表插入（List.Insert()）需要移动每个元素，因此速度较慢，

实际上，列表不会移动其值，而是迭代它们以查找要插入的位置，请注意您所说的话。这可能会让像我这样的新手感到困惑。

- nndhawan

Answer 6

有一种this数据结构，可以将插入时间从O(N)降至O(sqrt(N))，但我并不是很满意。我觉得应该能做得更好，但我需要再努力一些。

- Peter Gerdes

Answer 7

在C++中，您可以使用一个向量映射，像这样：

int main() {
  map<int, vector<int> > data;
  data[0].push_back(1);
  data[1].push_back(3);
  data[1].push_back(2);
  data[0].push_back(5);
  map<int, vector<int> >::iterator it;
  for (it = data.begin(); it != data.end(); it++) {
    vector<int> v = it->second;
    for (int i = v.size() - 1; i >= 0; i--) {
      cout << v[i] << ' ';
    }
  }
  cout << '\n';
}

这将打印：

5 1 2 3 

就像你想要的那样，插入操作的时间复杂度为O(log n)。

- Running Wild

---

如果你下一次尝试在第二个索引位置推入10，它将失败。 - amit