Efficient way to find the min and max value of a changing set in python

Question

I need to find the min/max value in a changing large set, in C++, it could be

#include<set>
using namespace std;
int minVal(set<int> & mySet){
    return *mySet.begin();
}
int maxVal(set<int> & mySet){
    return *mySet.rbegin();
}
int main(){
    set <int> mySet;
    for(..;..;..){
       // add or delete element in mySet
       ...
       // print the min and max value in the set
       printf("%d %d\n", minVal(mySet), maxVal(mySet)); 
    }
}

In C++, each query operation is O(1), but in python, I tried to use the build-in method min and max but it's too slow. Each min/max operation takes O(n) time (n is the length of my Set). Are there any elegant and efficient way to do this? Or any datatype support these operation?

mySet=set()
for i in range(..):
  # add or delete element in mySet
  ...
  # print the min and max value in the set
  print(min(mySet),max(mySet))

Answer 1

The efficient implementation in terms of complexity is wrapping a python set (which uses a hash table) and keeping a pair of maxElement and minElement attributes in the object, and updating those accordingly when adding or removing elements. This keeps every query of existence, min and max O(1). The deletion operation though would be O(n) worst case with the simplest implementation (since you have to find the next-to-minimum element if you happen to remove the minimum element, and the same happens with the maximum).

This said, the C++ implementation uses a balanced search tree which has O(log n) existence checks, deletion and insertion operations. You can find an implementation of this type of data structure in the bintrees package.

I wouldn't use just a heapq as suggested in comments as a heap is O(n) for checking existence of elements (main point of a set data structure I guess, which I assume you need).