在python中找到变化集的最小值和最大值的有效方法

Question

我需要在一个不断变化的大集合中找到最小值/最大值，在 C++ 中，它可能是

#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)); 
    }
}

在 C++ 中，每个查询操作都是 O(1)，但是在 python 中，我尝试使用内置方法 min 和 max 但它太慢了。每个最小/最大操作需要 O(n) 时间（n 是我的 Set 的长度）。有没有优雅有效的方法来做到这一点？或者任何数据类型支持这些操作？

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

在复杂性方面的有效实现是包装一个 python set（它使用一个哈希表）并在对象中保留一对maxElement和minElement属性，并在添加或删除元素时相应地更新这些属性。这保留了每个存在的查询，最小和最大 O(1)。但是，使用最简单的实现，删除操作将是 O(n) 最坏的情况（因为如果您碰巧删除了最小元素，则必须找到次最小元素，而最大值也是如此）。

这就是说，C++ 实现使用具有 O(log n) 存在检查、删除和插入操作的平衡搜索树。您可以在bintrees包中找到此类数据结构的实现。

我不会heapq像评论中建议的那样使用 a ，因为堆是 O(n) 来检查元素的存在（我猜是集合数据结构的主要点，我假设您需要）。