F#有效地从集合的末尾删除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

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

据我所知，没有。我想说的是，你有一个完美的实现，它运行在 O(lg n) 中——而且也很简洁:) 大多数堆实现无论如何都会为你提供 O(lg n) 的删除分钟，所以你所拥有的大约是尽可能好。

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

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

http://pastebin.com/j0aV3DJQ

我添加了一个split函数，它允许您获取一棵树并返回两棵树，其中包含所有小于给定值的值和所有大于给定值的值。split使用一次遍历树的时间复杂度为 O(lg n)，因此您可以一次修剪树的整个分支 - 前提是您知道要分割的值。

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

使用我的Treap课程：

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 是树中的项目数。

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