在O（ln n）中插入一個有序序列的值

Question

我正在python中尋找一個數據結構（在這個例子中用％劃定），它可以有效地（O（lnn）或更好的...）執行插入一個有序序列：

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

對於list和np.ndarray這是爲O（n）。 dict或set是無序的。

有沒有內建（或不）的方法來做到這一點？

Answer 1

List？

bisect可以幫助你，至少找那裏的元素應該插入的位置（O(log n)）時：

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

從文檔，但：

記住的是， O（log n）搜索主要是緩慢的O（n） 插入步驟。

所以列表確實是一個問題，而不是搜索本身。 Python TimeComplexity's table沒有顯示O（log n）插入的替代方案。

二叉搜索樹

從這個table，它看起來像「二叉搜索樹」具有O（log n）的用於訪問，搜索和插入。還有其他一些適合該法案的結構，但這可能是最知名的。

This answer (Implementing binary search tree) should help you。作爲一個例子：

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 

Answer 2

有多種數據結構可以做你想做的，但我不認爲有任何一個內置版本。您可以使用skip list或自平衡二分搜索索引（例如red-black樹，AVL tree）。有包裝包含那些結構。例如bintrees具有avl和紅黑樹的實現。