8

我不确定这是否可能，但对我来说似乎有点合理，我正在寻找一种允许我执行这些操作的数据结构：

  • 用 O(log n) 插入一个项目
  • 用 O(log n) 删除一个项目
  • 查找/编辑 O(1) 中的第 k 个最小元素，用于任意 k (O(1) 索引)

当然，编辑不会导致元素顺序发生任何变化。使之成为可能的原因是我将以递增的顺序一个接一个地插入元素。因此，例如，如果我尝试第五次插入，我确信在这之前的所有四个元素都比它小，而在这之后的所有元素都会更大。

4

6 回答 6

6

我不知道这样的数据容器是否可能需要请求的时间复杂度。但是这里有几种方法，几乎​​可以实现这些复杂性。

第一个是分层向量，插入和索引为 O(1)，但删除为 O(sqrt N)。由于您预计此容器中只有大约 10000 个元素并且 sqrt(10000)/log(10000) = 7，因此您在这里几乎可以获得所需的性能。分层向量被实现为一个环形缓冲区数组，因此删除一个元素需要移动所有元素，在环形缓冲区中跟随它，并将一个元素从后面的每个环形缓冲区移动到它之前的一个；在此容器中进行索引意味着在环形缓冲区数组中进行索引，然后在环形缓冲区内进行索引。

可以创建一个不同的容器，与分层向量非常相似，具有完全相同的复杂性，但工作速度更快一些，因为它对缓存更友好。分配一个 N 元素数组来存储值。并分配一个 sqrt(N) 元素数组来存储索引更正（用零初始化）。我将在 100 元素容器的示例中展示它是如何工作的。要删除索引为 56 的元素，请将元素 57..60 移动到位置 56..59，然后在索引更正数组中将 1 添加到元素 6..9。要找到第 84 个元素，在索引更正数组中查找第 8 个元素（其值为 1），然后将其值添加到索引 (84+1=85)，然后从主数组中取出第 85 个元素。删除主数组中大约一半的元素后，需要压缩整个容器以实现连续存储。这仅获得 O(1) 累积复杂度。对于实时应用程序，此操作可以在几个较小的步骤中执行。

这种方法可以扩展到深度为 M 的Trie，索引需要 O(M) 时间，删除需要 O(M*N 1/M ) 时间，插入需要 O(1) 时间。只需分配一个 N 元素数组来存储值 N (M-1)/M , N (M-2)/M , ..., N 1/M-元素数组来存储索引更正。要删除元素 2345，移动主数组中的 4 个元素，在最大的“更正”数组中增加 5 个元素，在下一个中增加 6 个元素，在最后一个中增加 7 个元素。要从此容器中获取元素 5678，请将元素 5、56、567 中的所有更正添加到 5678，并使用结果来索引主数组。为“M”选择不同的值，可以平衡索引和删除操作之间的复杂性。例如，对于 N=65000，您可以选择 M=4；所以索引只需要 4 次内存访问和删除更新 4*16=64 个内存位置。

于 2012-05-09T15:28:42.797 回答
1

我想首先指出，如果k真的是一个随机数，那么可能值得考虑问题可能完全不同：要求第 k 个最小的元素，k 在可用元素的范围内均匀随机基本上是......随机选择一个元素。它可以以不同的方式完成。

在这里，我假设您实际上需要选择一些特定的（如果是任意的）k。

鉴于您的元素按顺序插入的强前提条件，有一个简单的解决方案：

  • 由于您的元素是按顺序给出的，因此只需将它们一一添加到数组中；也就是说，您有一些（无限）表T和光标c，最初是c := 1，在添加元素时，执行T[c] := x和c := c+1。
  • 当你想访问第 k 个最小的元素时，只需查看 T[k]。

当然，问题是当你删除元素时，你会在表格中创建间隙，这样元素T[k]可能不是第 k 个最小的，而是j <= k的第 j 个最小的，因为有些k 之前的单元格为空。

然后，跟踪您已删除的元素就足够了，以了解已删除的小于k的元素数量。你如何在最多 O(log n) 的时间内做到这一点？通过使用范围树或类似类型的数据结构。范围树是一种结构，可让您添加整数，然后查询X和Y之间的所有整数。因此，每当您删除一个项目时，只需将其添加到范围树即可；并且在查找第 k 个最小元素时，查询0到k之间所有已删除的整数；说三角洲已被删除，则第 k 个元素将在 T[k+delta] 中。

有两个小问题，需要一些修复：

  • 范围树在 O(log n) 时间内返回范围，但是要计算范围中的元素数量，您必须遍历范围中的每个元素，因此这增加了时间 O(D)，其中 D 是范围内删除的项目；为了摆脱这种情况，您必须修改范围树结构，以便在每个节点处跟踪子树中不同元素的数量。保持这个计数只会花费 O(log n)，这不会影响整体复杂性，而且这是一个相当微不足道的修改。

  • 事实上，只进行一次查询是行不通的。实际上，如果您在 1 到 k 范围内获得 delta 已删除元素，那么您需要确保在 k+1 到 k+delta 范围内没有删除任何元素，依此类推。完整的算法将类似于下面的内容。

KthSmallest(T,k) := {
  a = 1;  b = k;  delta

  do {
    delta = deletedInRange(a, b)
    a = b + 1
    b = b + delta
  while( delta > 0 )

  return T[b]
}

此操作的确切复杂性取决于您删除的准确程度，但如果您的元素是随机均匀删除的，那么迭代次数应该相当少。

于 2012-05-08T22:59:23.253 回答
1

有一个Treelist（Java 的实现，带有源代码），所有三个操作（插入、删除、索引）的 O(lg n)。

实际上，这个数据结构的公认名称似乎是“订单统计树”。（除了索引之外，它还被定义为支持O(lg n) 中的indexof(element )。）

顺便说一句，与 O(lg n) 相比，O(1) 并没有被认为有太多优势。这种差异往往被实践中的恒定因素所淹没。（你会在数据结构中有 1e18 项吗？如果我们将其设置为上限，那仅相当于 60 左右的常数因子。）

于 2015-08-30T12:19:45.683 回答
0

查看成堆。插入和删除应该是 O(log n)，最小元素的窥视是 O(1)。然而，查看或检索第 K 个元素将再次花费 O(log n)。

已编辑：正如阿米特所说，检索比偷看更昂贵

于 2012-05-07T07:33:26.257 回答
0

这可能是不可能的。但是，您可以在平衡二叉树中进行某些更改以获得 O(log n) 中的第 k 个元素。

在此处阅读更多信息：维基百科。

于 2012-05-07T08:02:39.377 回答
0

可索引的跳过列表可能能够执行（关闭）您想要的操作： http ://en.wikipedia.org/wiki/Skip_lists#Indexable_skiplist

但是，有一些警告：

  1. 这是一个概率数据结构。这意味着它不一定是所有操作的 O(log N)
  2. 索引不会是 O(1)，只是 O(log N)
  3. 根据您的 RNG 的速度以及遍历指针的速度，您可能会从中获得更差的性能，而不仅仅是坚持使用数组并处理更高的移除成本。

最有可能的是，与此类似的事情将是您为实现目标所能做的“最好的”事情。

于 2012-05-07T08:13:06.370 回答