1

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

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')]

为什么最后两天不正常？是不是因为只有第一天保证是最小值，并且一旦我从堆中弹出第一天就会自动调整自己？

4

2 回答 2

5

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

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

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

于 2013-01-11T16:37:35.277 回答
1

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

于 2013-01-11T16:32:51.167 回答