python - 在 Python 中查找最小和最大元素

Question

假设我正在维护一组整数(将动态添加/删除，并且整数可能具有重复值)。我需要有效地找到当前元素集的最大/最小元素。想知道是否有更好的解决方案？

我目前的解决方案是维护一个最大堆和一个最小堆。我正在使用 Python 2.7.x 并为任何第 3 方 pip 插件打开以解决我的问题。

Answer 1

只需使用 min和 max功能。维护堆没有意义。如果要在添加删除元素时多次执行此操作(获取最小值/最大值)，则需要最小/最大堆。

不要忘记构建堆需要花费 O(n) 时间，其中常数为 2(据我所知)。只有这样，您才能使用它的 O(log(n)) 时间来获取您的最小值/最大值。

---

P.S. 好吧，既然你已经说过你必须多次调用最小/最大，你必须创建两个堆(最小堆和最大堆)。构建每个堆将花费 O(n)，然后每个操作(添加元素、删除元素、查找最小值/最大值)将花费 O(log(n)) ，您可以在其中向两个堆添加/删除元素，并在相应的堆上执行最小/最大操作。

就好像你将在列表上使用最小/最大函数一样，你不需要构造任何东西并且添加将花费 O(1)，删除 O(n) 和 min/max O(n)，这比堆差很多。

P.P.S python has heaps