1

minHeap と maxHeap の 2 つのヒープを作成するアルゴリズムがあります。2 つの唯一の違いは、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')]

最後の 2 日間はなぜ順不同なのですか? 最初の日だけが最小であることが保証されており、最初の日をポップすると、ヒープが自動的に調整されるためですか?

4

2 に答える 2

5

ヒープはソートされたリストではありません。ヒープは、たまたまリストとして保存される二分木です。ヒープの要素には、次のプロパティがあります。

a [k] <= a [2 * k+1]およびa[k]<= a [2 * k+2]のすべてのk

構造を理解するのに役立つ詳細な説明と優れた画像については、ドキュメントを参照してください：http: //docs.python.org/2/library/heapq.html#theory

于 2013-01-11T16:37:35.277 に答える
1

ヒープはソートされたリストではありません。これらは、最初の要素をすばやく取得できるリストであり、次の最初の要素を引き続きすばやく取得できるように構造を維持します。ヒープをリストとして見ると、要素は完全にソートされていません。

于 2013-01-11T16:32:51.167 に答える