Does python have a sorted list?

user_115200 0
Viewed 109232

By which I mean a structure with:

  • O(log n) complexity for x.push() operations
  • O(log n) complexity to find an element
  • O(n) complexity to compute list(x) which will be sorted

I also had a related question about performance of list(...).insert(...) which is now here.

list sorting python
9 Answers

The standard Python list is not sorted in any form. The standard heapq module can be used to append in O(log n) to an existing list and remove the smallest one in O(log n), but isn't a sorted list in your definition.

There are various implementations of balanced trees for Python that meet your requirements, e.g. rbtree, RBTree, or pyavl.

user_330060

Though it does not (yet) provide a custom search function, the heapq module may suit your needs. It implements a heap queue using a regular list. You'd have to write your own efficient membership test that makes use of the queue's internal structure (that can be done in O(log n), I'd say...). There is one downside: extracting a sorted list has complexity O(n log n).

user_749390

An AVL Tree [https://en.wikipedia.org/wiki/AVL_tree] coupled with in-order traversal will solve this problem in the required time complexity.

user_57129700

Interesting case: if your list L is already sorted (for example because you appended them in a sorted order), you can benefit from a fast lookup in O(log n) with a standard Python list with this method:

import bisect
def in_sorted_list(elem, sorted_list):
    i = bisect.bisect_left(sorted_list, elem)
    return i != len(sorted_list) and sorted_list[i] == elem
L = ["aaa", "bcd", "hello", "world", "zzz"]
print(in_sorted_list("hellu", L))       # False

More details in this answer.

user_14220960
Related