Efficient Sorted List Python
A regular red/black tree or B-tree can do this in an amortized sense. If you store pointers to the smallest and biggest elements of the tree, then the cost of deleting those elements is amortized O(1), meaning that any series of d deletions will take time O(d), though individual deletions may take longer than this. The cost of insertions are O(log n), which is as good as possible because otherwise you could sort n items in less than O(n log n) time with your data structure.
As for libraries that implement this - that I’m not sure of.
I am looking for a Python datastructure that functions as a sorted list that has the following asymptotics:

O(1) pop from beginning (pop smallest element)
O(1) pop from end (pop largest element)
>= O(log n) insert

Does such a datastructure with an efficient implementation exist? If so, is there a library that implements it in Python?