查找第k个最小元素数据结构

Question

我这里有一个问题，需要设计一个数据结构，对于以下三个操作采用 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) 部分。

大家有什么想法请分享。

Answer 1

想到了两种解决方案：

• 使用平衡二叉搜索树（红黑，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) 操作，但实现起来可能会有点长。

Answer 2

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

Answer 3

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

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

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

Answer 4

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

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

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

步骤 2.2 如果位置

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

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

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

Answer 5

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

有一种更好的方法来查找第 K 个最小元素，该方法依赖于中位数算法。基本上任何分区算法平均而言都足够好，但中位数中位数附带了最坏情况 O(N) 时间来查找中位数的证明。一般来说，该算法可用于查找任何特定元素，而不仅仅是中位数。

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

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

堆结构是一个很好的例子，快速排序算法也是如此。这是一个有效使用数组的非常有趣的例子（这个问题来自奥林匹克编程）：在数组中查找多数元素

Answer 6

我认为使用堆并没有那么糟糕。 您可以使用 max PriorityQueue 或 maxHeap。

在此方法中，您不必迭代所有值或 (k-1) 个值来获取第 k 个最小元素。

你可以这样做：-

PriorityQueue<Integer> pq = new PriorityQueue<>(Collections.reverseOrder());
public void set(int i ){
    pq.set(i);

    if(pq.size() > k){
        pq.poll();
    }
}

public int get(){
    return pq.peek();
}