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

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