6

私はこのようなヒープ（python、heapqモジュール）を持っています -

>>> h = []
>>> heappush(h, (5, 'write code'))
>>> heappush(h, (7, 'release product'))
>>> heappush(h, (1, 'write spec'))
>>> heappush(h, (3, 'create tests'))

O(logn)で「テストの作成」として項目値を持つタプルを削除し、ヒーププロパティを保持するにはどうすればよいですか?

これは私が思いついたものです（O（logn）ではありません）

for i in range(len(h)):
   if h[i][1] == "create tests":
      h[i], h[-1] = h[-1], h[i]
      popped = h.pop()
      heapq.heapify(h)
      break
4

5 に答える 5

19

アイテムを取り出す必要があるheapが、保存したいheap場合は、リストを検索するのではなく、怠惰にそれを行い、アイテムが自然に出てきたときに破棄することができます。

削除するアイテムをブラックリストに保存する場合は、そのアイテムがにあるかどうかsetを確認するたびに。それが存在する場合は、ブラックリストに載っていないものが得られるまで、または空になるまで、それを破棄してください。heapq.heappopsetheappopheap

于 2012-12-10T12:50:57.837 に答える
0

heapqだけではそのような方法はないのではないかと思います。ヒープから要素を検索するには。が必要O(n)です。

ただし、エントリを検索する時間dictを与えるのようなものと一緒に使用できます。O(1)

更新しました：

簿記に辞書を使ってみましたが、挿入されたときに「テストの作成」のインデックスを取得するにはどうすればよいですか？–プラカール3時間前

素朴なアプローチは次のようになります。

# remember to update this hdict when updating the heap.
hdict = { h[i][1]: i for i in range(len(h)) }

次に、線形検索hdictの代わりにこれにアクセスすることで、特定の文字列のインデックスを取得できます。O(n)

于 2012-12-10T12:42:47.943 に答える