5

我这里有一个问题，需要设计一个数据结构，该结构在以下三个操作中采用 O(lg n) 最坏情况：

  a) Insertion: Insert the key into data structure only if it is not already there.
  b) Deletion: delete the key if it is there!
  c) Find kth smallest : find the ݇k-th smallest key in the data structure

我想知道我是否应该使用堆，但我仍然没有一个明确的想法。
我可以很容易地得到 O(lg n) 的前两部分，甚至更快，但不知道如何处理 c) 部分。

任何人有任何想法请分享。

4

5 回答 5

8

想到了两个解决方案：

  • 使用平衡的二叉搜索树（红黑、AVG、Splay，......任何都可以）。您已经熟悉操作 (1) 和 (2)。对于操作 (3)，只需在每个节点存储一个额外的值：该子树中的节点总数。您可以轻松地使用此值找到 O(log(n)) 中的第 k 个最小元素。例如，假设你的树如下 - 根 A 有 10 个节点，左孩子 B 有 3 个节点，右孩子 C 有 6 个节点（3 + 6 + 1 = 10），假设你想找到第 8 个最小的元素，你知道你应该去右边。

  • 使用跳过列表。它还平均支持所有 O(logn) 的 (1)、(2)、(3) 操作，但实现时间可能要长一些。

于 2012-04-09T03:24:54.550 回答
6

好吧，如果您的数据结构保持元素排序，那么很容易找到第 k 个最低的元素。

于 2012-04-09T01:09:09.840 回答
1

用于搜索和插入的二叉搜索树的最坏情况成本是 O(N)，而平均情况成本是 O(lgN)。

因此，我建议使用红黑二叉搜索树，它保证搜索和插入的最坏情况复杂度为 O(lgN)。

您可以在此处阅读有关红黑树的更多信息，并在此处查看Java 中红黑 BST 的实现。
因此，就使用上述红黑 BST 实现查找第 k 个最小元素而言，您只需调用select方法，传入k的值。select方法还保证了最坏情况的O(lgN)。

于 2012-04-09T01:23:54.237 回答
0

解决方案之一可能是使用快速排序策略。

步骤 1：选择第一个元素作为枢轴元素并将其带到正确的位置。（最多 n 次检查）现在，当您到达此元素的正确位置时，您将进行检查

步骤 2.1：如果 location >k 您的元素位于第一个子列表中。所以你对第二个子列表不感兴趣。

步骤 2.2 如果位置

步骤 2.3 如果 location == k 你已经让元素破坏了外观/递归

第 3 步：使用适当的子列表重复第 1 步到第 2.3 步

该解决方案的复杂度为 O(n log n)

于 2012-10-22T15:54:32.673 回答
0

堆不是查找数组中第 K 个最小元素的正确结构，因为您必须从堆中删除 K-1 个元素才能找到第 K 个元素。

找到第 K 个最小元素的方法要好得多，它依赖于中位数算法。基本上任何分区算法平均来说都足够好，但是中位数的中位数伴随着最坏情况 O(N) 时间的证明来找到中位数。通常，该算法可用于查找任何特定元素，而不仅仅是中位数。

下面是这个算法在C#中的分析和实现：Finding Kth Smallest Element in an Unsorted Array

PS 在相关说明中，您可以使用数组就地执行许多操作。数组是一种奇妙的数据结构，只有当您知道如何在特定情况下组织其元素时，您才能非常快速地获得结果并且无需额外的内存使用。

堆结构就是一个很好的例子，快速排序算法也是如此。这是一个有效使用数组的非常有趣的例子（这个问题来自编程奥运会）：Finding a Majority Element in an Array

于 2013-07-19T09:06:27.287 回答