4

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 ?

B. M.
  • 18,243
  • 2
  • 35
  • 54
  • Have you looked into ordered dict? – Julien Mar 19 '17 at 09:29
  • It seems it keeps inserting order, not value order. – B. M. Mar 19 '17 at 09:37
  • You can trade O(1) indexing for O(log n) indexing to get O(log n) insertion with a binary search tree like a [red-black tree](https://en.wikipedia.org/wiki/Red%E2%80%93black_tree), or O(1) indexing for O(n) indexing in a linked list to get O(1) insertion relative to a node you have. More context, please? (i.e. what are you using this data structure for?) – Ry- Mar 19 '17 at 09:43
  • See [Time Complexity](https://wiki.python.org/moin/TimeComplexity) – Peter Wood Mar 19 '17 at 09:43

2 Answers2

4

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
Community
  • 1
  • 1
Eric Duminil
  • 52,989
  • 9
  • 71
  • 124
  • Unfortunately , `insort_left` doc says : Keep in mind that the O(log n) search is dominated by the slow O(n) insertion step. – B. M. Mar 19 '17 at 09:35
3

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.

Ivaylo Strandjev
  • 69,226
  • 18
  • 123
  • 176
  • Thanks for your accurate answer. I will try all the trees of the forest to find the best for me. – B. M. Mar 19 '17 at 12:06