9

アルゴリズムを実装するためにヒープ キューを使用しています。新しいノードをキューに追加すると、ヒューリスティック関数によって並べ替えられます。キューから次のノードをポップするときに、最初に追加されたノードではなく、最後に追加されたノードが必要であるという事実から、heappop が返します。キューを壊さずにキューに追加された最新のノードを取得するにはどうすればよいですか?

最初の要素から反復を開始し、次の要素のスコアが同じである間は続行できると思います。次に、そのスコアを持つ最後の要素を見つけたら、それを選択してリストから削除します。これは明らかにあまり効率的ではなく、優先キューの時間の複雑さを解消しますか?

私はこれに行き詰まっており、それを行う方法がわかりません。

ありがとう。

編集; 提案されているようにカウンターを使用しても機能しません（おそらく私は誤解しています）

>>> queue = []
>>> heappush(queue, (2, 0, 'a'))
>>> heappush(queue, (3, -1, 'b'))
>>> queue
[(2, 0, 'a'), (3, -1, 'b')]
>>> heappush(queue, (2, -2, 'c'))
>>> queue
[(2, -2, 'c'), (3, -1, 'b'), (2, 0, 'a')]

現在、キューの順序が正しくなく、'a' よりも悪いオプションである 'b' がその前に配置されています。

編集2：

なんてこったい？

>>> heappop(queue)
(2, -2, 'c')
>>> queue
[(2, 0, 'a'), (3, -1, 'b')]
>>>
4

1 に答える 1

12

非常に簡単な方法の 1 つは、タイムスタンプまたはカウンター値を含む中間項を追加することです。たとえば、次のようになります。

>>> heap = []
>>> counter = itertools.count()
>>> for i in range(10):
...     heapq.heappush(heap, (i, -next(counter), str(i) + ' oldest'))
...     heapq.heappush(heap, (i, -next(counter), str(i) + ' newest'))
... 
>>> heapq.heappop(heap)
(0, -1, '0 newest')
>>> heapq.heappop(heap)
(0, 0, '0 oldest')
>>> heapq.heappop(heap)
(1, -3, '1 newest')
>>> heapq.heappop(heap)
(1, -2, '1 oldest')

agf が言及しているように、これはheapqドキュメントで使用されているアプローチであり、負のインデックスのみを使用しています。(そこの実装には、素敵なタスクの削除と優先度の変更ルーチンも含まれています。)

于 2012-04-18T22:30:09.683 に答える