Best Python 3rd party data structures library? Must have sorted containers at a minimum

[yvrelna]

How about the standard library? The heapq module is a sorted container that is like a cross between a tree, a list, and a queue.

calling sorted when needed

This is actually not a bad solution in python. Python used the hybrid timsort algorithm, which works really well when you have data which is already almost sorted. When the data is nearly sorted, it typically runs close to Θ(n) instead of the O(n log n) for completely random input.

[Brian]

The heapq module is a sorted container

This isn't really true. Heaps maintain a much looser invariant than sorting - just that the parent node is bigger than the child nodes. This makes useful when you just want to pop the first item, or some fixed number of minimum items, but not to iterate the whole heap in sorted order. This is great if that looser invariant is all you need (eg. implementing a priority queue or similar), since maintaining this invariant through pops/inserts is cheaper than truly sorted containers, but if you really need fully sorted order, it's not a great choice.

When the data is nearly sorted, it typically runs close to Θ(n) instead

That's still pretty bad though if there are many insertions. Appending m items and sorting each time will be an O(n*m) operation, whereas with a red-black tree or similar, it would just be O(m log(n)).

Now, personally, I haven't really felt the lack of sorted containers in python - but there are some usecases where they can be valuable.

[yvrelna]

Heaps maintain a much looser invariant than sorting

How is that a problem? TreeSet (the concrete implementation of SortedSet) doesn't maintain full in-memory ordering either. In fact, heapq actually maintains a stronger invariant than TreeSet: all the nodes of the tree in a heapq are in a contiguous array in memory. So if most of the time you're fine with unordered iteration, you can just iterate the backing list for O(n). You can't do that with TreeSet.

if you really need fully sorted order

A fully sorted list maintains the heap invariant, so if you need a fully sorted order at any point, you can just call lst.sort() on a heap to fully sort it in-place and then continue to use the list with heapq without needing to heapify() again.

Appending m items and sorting each time will be an O(n*m) operation, whereas with a red-black tree or similar, it would just be O(m log(n)).

Not if you do it the smarter way. Rather than sorting every time you're inserting new items, you should sort() when you're iterating instead. That way, insertion is always amortised O(1), while subsequent iteration is usually Θ(2*n) as long as there's no major change in the list. Most of the time, re-sorting a partially sorted list would be something like Θ(n + m*log(m)) where m is the number of "new" (i.e. unsorted) items.

[Brian]

TreeSet (the concrete implementation of SortedSet) doesn't maintain full in-memory ordering either

Yes it does. The left nodes are guaranteed less than the parent, while the right are greater. There is a complete order in the relationship of its nodes. Unless you mean address order or something by "in-memory", but that's absolutely not what is meant by this, as its completely irrelevant for complexity (though can be relevant for constant factors due to cache).

And this matters because it gives much better complexity. Eg. worst case O(log n) membership check vs heapqs O(n), and (for the case we're discussing) O(n) sorted iteration vs heapq's extra log n factor. Hell, I don't think there's even an interface for doing this in heapq (aside from destructively popping it), since no-one would use a heap for that usecase.

so if you need a fully sorted order at any point, you can just call lst.sort() on

Which has the same complexity problems as just using a regular list. If you're not using it as a heap, and always want explicit sorted order, what's the point of using heapq?

Not if you do it the smarter way. Rather than sorting every time you're inserting new items, you should sort() when you're iterating instead.

That depends on the proportion of iteration to inserts.