CODEWITHSUNDEEP
pythonperformancedata-structures
B. M.
B. M.

Reputation: 18638

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

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 ?

Upvotes: 4

Views: 868

Answers (2)

Ivaylo Strandjev
Ivaylo Strandjev

Reputation: 70939

There are multiple data structures that can do what you want, but I don't think there is a built in version of any of them. You can use a skip list or a self balancing binary search ree (e.g. red-black tree, AVL tree). There are side packages that contain those structures. For instance bintrees has implementations for avl and red black trees.

Upvotes: 3

Eric Duminil
Eric Duminil

Reputation: 54233

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

Upvotes: 4

Related Questions