python - 在 O(ln n) 的有序序列中插入一个值

Question

我正在 python 中寻找一种数据结构(在此示例中由 % 分隔)，它可以高效地(O(ln n) 或更好...)按有序序列执行插入:

insert ( 6, % 3, 4, 9 %) ->  % 3, 4, 6, 9 %

对于 list 和 np.ndarray 它是 O(n)。 dict 或 set 是无序的。

是否有内置(或不内置)方法来做到这一点？

Answer 1

列表 ?

bisect可以帮助你，至少在寻找应该插入元素的位置时 (O(log n)) :

import bisect
l = [3, 4, 9]
bisect.insort_left(l , 6)
print(l)
# [3, 4, 6, 9]

不过，从文档来看:

Keep in mind that the O(log n) search is dominated by the slow O(n) insertion step.

所以list确实是个问题，而不是搜索本身。 python TimeComplexity's table没有显示 O(log n) 插入的任何替代方案。

二叉搜索树

从这里table ，看起来“二叉搜索树”的访问、搜索和插入时间复杂度为 O(log n)。还有其他符合要求的结构，但这可能是最广为人知的。

这answer (Implementing binary search tree)应该帮助你。举个例子:

r = Node(3)
binary_insert(r, Node(9))
binary_insert(r, Node(4))
binary_insert(r, Node(6))

in_order_print(r)
# 3
# 4
# 6
# 9