堆和负数的奇怪行为

Question

我有一个创建两个堆的算法，minHeap 和 maxHeap。两者之间的唯一区别是 maxHeap 反转了 minHeap 的符号，这是使用 Python 的 heapq 数据结构作为最大堆的简单技巧。这是我创建堆的代码（堆键基本上是一周中给定日期字典中的工作人员数量）：

for day in self.weekDict:
    if day != 'Saturday' and len(self.weekDict[day]) != 0: #saturdays and holidays not part of optimization
        heapq.heappush(minHeap, (len(self.weekDict[day]), day))
        heapq.heappush(maxHeap, (-len(self.weekDict[day]), day))

minHeap 按预期工作，但是当有多个相同的键时，最大堆会给我带来奇怪的行为。见下文：

[(-8, 'Thursday'), (-7, 'Monday'), (-5, 'Friday'), (-7, 'Wednesday'), (-7, 'Tuesday')]

为什么最近两天不正常？是不是因为只有第一天才能保证是最小值，一旦我弹出第一天，堆就会自动调整？

Answer 1

堆不是排序列表。堆是一棵二叉树，它恰好存储为一个列表。堆的元素具有以下属性：

a[k] <= a[2*k+1] 和 a[k] <= a[2*k+2] 对于 a 中的所有 k

请参阅文档以获得更完整的解释和漂亮的图片以帮助遵循结构：http : //docs.python.org/2/library/heapq.html#theory