algorithm - 如何在集合可能随时间变化的情况下有效地找到集合中的第 k 个最大元素？

Question

有一些查询可以询问集合中的第 k 个最大元素。

并且有一些更新可以添加、删除或更改元素。

如何有效地完成这项任务？

提前致谢。

Answer 1

二叉搜索树（针对每个节点进行修改以存储来自该节点的子树的大小）应该可以解决问题。

找到第 k 个最大的将需要O(log n)时间。

添加、删除和更新（删除，然后添加）每个都需要 <=O(log^2 n)时间（或者可能只是O(log n)）。

根据查找数据的方式，您可能需要一个带有指向 BST 的指针的数组或哈希映射（用于更新操作）。

查找第 k 个最大的将如下所示：

Node findKthLargest(Node node, int k)
  if (node.left != null)
    if (k <= node.left.count)
      return findKthLargest(node.left, k)
    else
      k -= node.left.count
  if (k == 0)
    return node
  if (node.right != null)
    return findKthLargest(node.right, k)

由于它不能同时探索left和right，很明显它只需要O(log n)时间。

添加、删除和更新将不得不修改适当的子树计数，但仅限于树中较高的那些。因为使用平衡二叉搜索树，这些操作（没有计数修改）每个都需要O(log n)时间，而随着计数修改，您只O(log n)需要在每个步骤中做额外的工作（上树）O(log n)，所以显然它不能超过O(log^2 n).