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

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

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

最佳答案

有两种解决方案:

使用平衡的二进制搜索树(红黑色，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)操作，但是实现起来可能会更长一些。

关于algorithm - 查找第k个最小的元素数据结构，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/10067881/