是否存在表示主要操作的O(n * log n)时间的有序列表的数据结构?

问题描述 投票:1回答:1

我正在寻找一种数据结构,允许在O(n * log(n))复杂度中解决特定问题。它需要表示一组整数,我可以在其中执行以下操作: - 添加元素 - 检查集合中是否存在元素 - 删除大于给定整数的每个值希望具有对数复杂度。

我寻找链表,因为在中间添加一个元素并删除结构的整个部分很容易,但我不知道如何保持有序列表或实现二分法搜索。起初我正在考虑哈希表,但我不知道如何过滤该集。我正在寻找平衡的二叉树,我不知道我是在寻找妄想的东西,还是以某种方式存在,而我却找不到它。

algorithm list sorting set structure
1个回答
0
投票

为了从头开始实施,我建议使用Treap

Treap只是一个二叉搜索树,每个节点都有一个随机优先级,它满足堆条件作为树。这种随机数据结构使得查找,插入,删除和拆分树的预期时间为O(log(n))。前三个相当简单。要进行拆分,只需将节点放在要以优先级高于根的优先级进行拆分的位置。然后一半在该节点的一侧缠绕,另一半在另一侧缠绕。

请注意,虽然拆分是O(log(n)),释放删除的位是O(n)

请注意,您可能无需执行任何操作。例如,在C ++中,您可以使用std::map。除删除之外的那些操作的性能是O(log(n))。虽然从m大小的结构中删除长度n的范围是O(m + log(n))。如果你考虑关于释放内存的评论,那就是理想的。

热门问题
推荐问题
最新问题