python - 与Mines和Maxes合作-Heapq合适吗？

Question

我有一个调度算法，我比较优先级/任务元组列表的最小值和最大值，对它们执行一些更改优先级的操作，然后将它们重新插入到列表中，并适当地更新列表。heapq是最好的数据结构吗？如何在不弹出的情况下进行初始比较（基本上是确定优先级值是否相距足够远，需要进一步操作；如果不是，函数将停止）？一旦做了比较，我将如何把最大值和最小值放在一起，因为heapq是专为弹出最小值而设计的？

Answer 1

heapq只提供一个最小堆，也就是说，您可以在o（log n）时间内弹出min值，但不能弹出max值。
如果需要类似于heapq的双面数据结构，有几个基本选项。
首先，常规最小堆有什么问题不仅仅是api；找到最大值需要O(n)时间而不是O(1)时间，因此弹出它需要O(n)而不是O(log n)，这是您需要改进的关键。
一个简单的技巧是保留两个堆，一个具有正常值，一个具有修饰的正常值，以便它们向后排序下面是伪代码的实现：

def push(self, value):
    insert into both normal and reversed heaps
def minpop(self):
    check that the min value of normal hasn't reached the min value of reversed
    pop and return the min value of normal
def maxpop(self):
    check that the min value of reversed hasn't reached the min value of normal
    pop and return the min value of reversed

乍一看，每个操作的最坏情况应该是minheap的两倍，但事实并非如此。特别是，最坏情况下的空间是插入的元素数，它可能比插入的元素数（删除的元素数）高得多。（例如，如果您插入了1000个项目并删除了100个，900>>200。）
有许多这样做行不通的用例，如果它在您的用例中行不通，那就很明显了但如果合适的话，那就太简单了。
如果不合适，可以使用真正的最小最大堆这基本上只是将一个最小堆的 normal和 reversed版本交错到一个结构中，使得在上面的“check”情况下很容易做正确的事情（而不是留下值）。
但是，如果您想要双端优先级队列的对称性能，那么您实际上做不到比平衡树或skiplist更好的事情。（好吧，不是一般用途。如果你有特定的行为特征，那可能不是真的。）而且有很多avl树、红黑树和skiplits的实现，比min max二进制堆多得多。所以，搜索pypi和activestate菜谱中的“平衡树”、“红黑树”、“avl树”、“skiplist”等，你会发现像 bintrees和 skiplist这样的东西，它们都应该有效。
不过，我还是推荐 blist。它使用平衡树和数组的特殊混合，而不是经过仔细研究的数据结构，乍一看可能会让您觉得它不太可信。不过，我相信它比任何竞争模块都得到更多的使用和实际测试，而且它也得到了相当大的优化。（当您处理 A * log Bn + C性能时，更改 A或 C通常比更改 B有更大的影响）实际上它还有一个很好的界面，其中一些界面如果您使用 blist.sortedlist，您只需执行 sl[0]、 sl[-1]、 sl.pop(0)、 sl.pop(-1)和 sl.add(x)，几乎与您预期的完全一样。
所以，你的代码应该是这样的（如果我理解你的英文描述）：

class MyQueue(object):
    def __init__(self):
        self.sl = blist.sortedlist(key=operator.itemgetter(0))
    def add(self, priority, task):
        self.sl.add((priority, task))
    def step(self):
        if self.sl[-1][0] - self.sl[0][0] < MyQueue.EPSILON:
            return
        minprio, mintask = self.sl.pop(0)
        maxprio, maxtask = self.sl.pop(-1)
        newminprio, newmaxprio = recalc_priorities(minprio, maxprio)
        self.add(newminprio, mintask)
        self.add(newmaxprio, maxtask)

任何这些方法的问题是，最坏的情况下，窥视双方是 O(log N)而不是 O(1)但是，如果您只需要执行这些操作，那么有一个简单的方法：将这些值缓存起来：

class MyQueue(object):
    def __init__(self):
        self.sl = blist.sortedlist(key=operator.itemgetter(0))
        self.minprio, self.maxprio = None, None
    def add(self, priority, task):
        self.sl.add((priority, task))
        if prio < self.minprio: self.minprio = prio
        elif prio > self.maxprio: self.maxprio = prio
    def step(self):
        if self.maxprio - self.minprio < MyQueue.EPSILON:
            return
        minprio, mintask = self.sl.pop(0)
        maxprio, maxtask = self.sl.pop(-1)
        newminprio, newmaxprio = recalc_priorities(minprio, maxprio)
        self.add(newminprio, mintask)
        self.add(newmaxprio, maxtask)
        self.minprio, self.maxprio = sl[0][0], sl[-1][0]

这使得通过 step O(1)而不是 O(log n)的快速路径，并使所有现有的 O(log n)操作仍然 O(log n)。
另请参见 Wikipedia了解可以替换此处可能相关的二进制堆的其他类型堆的讨论。
最后一点，igorrs的评论提醒我：
这里有各种不同的数据结构，它们会给你带来相同的最坏算法复杂度。有时，任何避免 O(n)的方法都足够好，所以您应该只使用最简单的实现并完成它。但有时（特别是对于许多手术，但是很小的 n，或者数据不典型的情况），常数因子、最佳情况等会产生巨大的差异。在这种情况下，正确的做法是构建多个实现并使用真实数据进行测试，看看什么是最快的。