algorithm - 寻找第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 个节点，左 child B 有 3 个节点，右 child C 有 6 个节点(3 + 6 + 1 = 10)，假设你想找到第 8 个最小的元素，你知道你应该走到右边。

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