找到第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个最小元素,你知道你应该去右边.

• 使用跳过列表.它还支持平均所有(1),(2),(3)O(logn)操作,但实现起来可能要长一些.

Answer 2

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