Does python have a sorted list?

Question

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.

Answer 1

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

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

Answer 2

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).