堆和负数的奇怪行为

Question

我有一个算法可以创建两个堆，minHeap和maxHeap。两者之间唯一的区别是maxHeap颠倒了minHeap的符号，这是一种将Python的heapq数据结构用作max heap的简单方法。下面是我创建堆的代码（heap键基本上是字典中给定一周中某一天的工人数）：

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的工作与预期一样，但是当有多个相同的键时，max heap给出了奇怪的行为。见下文：

^{pr2}$

为什么最近两天不正常？是不是因为只有第一天被保证是最小值，而且一旦我把第一天从堆里弹出，它就会自动调整自己？在

Answer 1

堆不是排序列表。它们是一个列表，您可以从中快速提取第一个元素，还可以保持结构，以便您可以继续快速提取下一个第一个元素。当您将堆视为一个列表时，元素将不会完全排序。在

Answer 2

堆不是已排序的列表。堆是一个二叉树，它碰巧以列表的形式存储。堆的元素具有以下属性：

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

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