data-structures - F# 有效地从 Set 的末尾删除 n 个项目

Question

我知道我可以从集合中删除最后一个元素:

s.Remove(s.MaximumElement)

但是，如果我想删除 n 个最大元素……我是只执行上述 n 次，还是有更快的方法来做到这一点？

需要明确的是，这是一个显而易见的解决方案:

let rec removeLastN (s : Set<'a>, num : int) : Set<'a> = 
    match num with
    | 0 -> s
    | _ -> removeLast(s.Remove(s.MinimumElement), num-1)

但它涉及创建一个新集合 n 次。有没有办法做到这一点并且只创建一次新集合？

Answer 1

But it involves creating a new set n times. Is there a way to do it and only create a new set once?

据我所知，没有。我会说你有一个完美的实现，它在 O(lg n) 中运行——而且它也很简洁:) 大多数堆实现都给你 O(lg n) 来删除 min，所以你所拥有的是很好，你可以得到它。

您可以通过滚动平衡树并实现一个函数来为大于某个值的所有值删除左分支或右分支，从而获得更好的速度。我认为 AVL 树或 RB 树在这种情况下不合适，因为您无法真正维护它们的不变量，但是随机化树会给您想要的结果。

一个 treap 对此非常有用，因为它使用随机化而不是树不变量来保持自身相对平衡。与 AVL 树或 RB 树不同，您可以在节点上拆分 treap，而不必担心它不平衡。这是我几个月前写的一个 treap 实现:

http://pastebin.com/j0aV3DJQ

我添加了一个 split函数，它将允许您获取一棵树并返回包含所有小于给定值和所有值大于给定值的两棵树。 split使用一次遍历树以 O(lg n) 运行，因此您可以一次性修剪树的整个分支——前提是您知道要拆分的值。

But if I want to remove the n maximum elements... do I just execute the above n times, or is there a faster way to do that?

使用我的 Treap类(class):

open Treap

let nthLargest n t = Seq.nth n (Treap.toSeqBack t)
let removeTopN n t =
    let largest = nthLargest n t
    let smallerValues, wasFound, largerValues = t.Split(largest)
    smallerValues

let e = Treap.empty(fun (x : int) (y : int) -> x.CompareTo(y))
let t = [1 .. 100] |> Seq.fold (fun (acc : Treap<_>) x -> acc.Insert(x)) e
let t' = removeTopN 10 t

removeTopN在 O(n + lg m) 时间内运行，其中 n 是树序列的索引，m 是树中的项目数。

我不保证我的代码的准确性，使用后果自负；)