Inserting a value in a ordered sequence in O(ln n)

Question

I am looking for a data structure (delimited by % in this exemple) in python, which can efficiently (O(ln n) or better...) perform insertion in a ordered sequence:

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

For list and np.ndarray it's O(n). dict or set are unordered.

Is there a builtin (or not) way to do that ?

Answer 1

List ?

bisect could help you, at least when looking for the position where the element should be inserted (O(log n)) :

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

From the documentation, though :

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

So list is indeed a problem, not the search itself. Python TimeComplexity's table doesn't show any alternative with O(log n) insertion.

Binary Search Tree

From this table, it looks like "Binary Search Tree" has O(log n) for Access, Search and Insertion. There are other structures that fit the bill as well, but this might be the most well-known.

This answer (Implementing binary search tree) should help you. As an example :

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