如何在集合中高效地找到第k個最大元素，而集合可能隨時間變化？

Question

有一些查詢要求集合中的第k個最大元素。

還有一些更新可以添加，刪除或更改元素。

如何有效地完成這項任務？

在此先感謝。

Answer 1

A Binary Search Tree（修改爲每個節點存儲從該節點的子樹的大小）應該做的伎倆。

查找第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)。