43

O(log n) でキーの減少機能を実現できることは知っていますが、方法がわかりません。

4

6 に答える 6

43

「decrease-key」を効果的に実装するには、「この要素をデクリメントし、ヒープ状態が復元されるまで、この要素を子と交換する」機能にアクセスする必要があります。heapq.pyでは、それが呼び出されます_siftdown(同様_siftupに INcrementing についても)。良いニュースは、関数がそこにあるということです...悪いニュースは、それらの名前がアンダースコアで始まることです。これは、それらが「内部実装の詳細」と見なされ、アプリケーション コードから直接アクセスされるべきではないことを示しています (標準ライブラリは、そのような「内部」を使用して物事を変更し、コードを壊す可能性があります)。

警告の先頭を無視するか、O(log N) ふるい分けの代わりに O _(N) を使用するheapifyか、または heapq の機能の一部またはすべてを再実装して、ふるい分けプリミティブを「の公開部分として公開する」かどうかは、あなた次第です。インターフェース"。heapq のデータ構造は文書化されて公開されているため (リストのみ)、おそらく部分的な再実装が最善の選択であると思います。本質的に、ふるい分け関数を heapq.py からアプリケーション コードにコピーします。

于 2009-09-23T14:41:15.073 に答える
6

ヒープを優先キューとして使用していると想像してください。ここでは、文字列で表される一連のタスクがあり、各タスクにはキーがあります。具体的には、次を参照してくださいtask_list = [[7,"do laundry"], [3, "clean room"], [6, "call parents"]]。 各タスクtask_listは、優先度と説明を含むリストです。を実行するheapq.heapify(task_list)と、配列がヒープ不変を維持します。ただし、「洗濯をする」の優先度を 1 に変更したい場合は、ヒープ全体を線形スキャンしないと、「洗濯をする」がヒープのどこにあるかを知る方法がありません (したがって、対数時間で reduce_key を実行することはできません)。 . decrease_key(heap, i, new_key)ヒープ内で変更する値のインデックスを知っている必要があることに注意してください。

各サブリストへの参照を維持し、実際にキーを変更したとしても、ログ時間内にそれを行うことはできません。リストは一連の変更可能なオブジェクトへの単なる参照であるため、タスクの元の順序を覚えているようなことを試すことができます (この場合、「洗濯をする」は元の 0 番目のタスクでしたtask_list):

task_list = [[7, "do laundry"], [3, "clean room"], [6, "call parents"]]
task_list_heap = task_list[:] # make a non-deep copy
heapq.heapify(task_list_heap)
# at this point:
# task_list = [[7, 'do laundry'], [3, 'clean room'], [6, 'call parents']]
# task_list_heap = [3, 'clean room'], [7, 'do laundry'], [6, 'call parents']]
# Change key of first item of task_list (which was "do laundry") from 7 to 1.
task_list[0][0] = 1
# Now:
# task_list = [[1, 'do laundry'], [3, 'clean room'], [6, 'call parents']]
# task_list_heap = [3, 'clean room'], [1, 'do laundry'], [6, 'call parents']]
# task_list_heap violates heap invariant at the moment

heapq._siftdown(task_list_heap, 1)ただし、ログ時間 ( は線形時間) でヒープの不変を維持するために呼び出す必要がありますheapq.heapifyが、残念ながら、「洗濯を行う」のインデックスはわかりませんtask_list_heap(heap_indexこの場合は 1 です)。

heap_indexそのため、ヒープが各オブジェクトの追跡を維持するように実装する必要があります。たとえば、list（ヒープ用）およびdict各オブジェクトをヒープ/リスト内のインデックスにマッピングします（ヒープ位置がスワップされると更新され、各スワップに定数係数が追加されます）。手順は簡単なので、heapq.pyを読んで自分で実装することができます。ただし、他の人はこの種のHeapDictを既に実装しています。

于 2012-12-10T15:47:50.463 に答える
2

この機能は不要かもしれませんdecrease_key(あると便利ですが)。

いずれにせよ、あなた(priority, item)を優先キューにプッシュし、 a を使用しsetてそれを見たかどうかを確認できます。例えば：

pq = []  # heapq is a min heap
seen = set()
heappush(pq, (2, "item1"))
heappush(pq, (3, "item2"))
heappush(pq, (1, "item3"))
heappush(pq, (4, "item4"))
heappush(pq, (2, "item2"))

while pq:
    p, item = heappop(pq)
    if item not in seen:
        seen.add(item)
        print(item, p)
    else:
        print(item, "is already handled with a higher priority!")

出力は次のとおりです。

item3 1
item1 2
item2 2
item2 is already handled with a higher priority!
item4 4
于 2021-02-03T09:46:14.233 に答える