0

ヒープ データ構造を使用して解決する必要がある問題を解決しています。操作は挿入と抽出分によって支配されますが、アイテムのキーを置き換える (増加または減少させる) か、アイテム、キーを完全に削除する必要がある場合があります。モジュールはこれらの操作を提供せheapqず、ヒープ内のアイテムを検索するのはO(n).heapifyヒープ プロパティ - これらの操作のすべてが で実行されO(logn)ます。ただし、問題は、そのような辞書を実装できないことです。

h, bkp = [], {}
heappush(h, (5, 'a'))
bkp['a'] = # index of 'a' in heap
heappush(h, (7, 'b'))
bkp['b'] = # index of 'b' in heap
heappush(h, (1, 'c'))
bkp['c'] = # index of 'c' in heap

# deleting 'a'
h[bkp['a']], h[-1] = h[-1], h[bkp['a']]
h.pop()
heapify(h) 

#update indices in bkp

質問 - ヒープに新しく挿入されたアイテムのインデックスを見つけるにはどうすればよいですか? また、削除またはプッシュ操作の後、ヒープ内の既存のアイテムのインデックスを再計算するにはどうすればよいですか?

4

1 に答える 1

0

これを行うにはいくつかの方法があります。

1 つのオプションは、各オブジェクトの位置をオブジェクト自体に格納することで、ヒープを邪魔にならないようにすることです。そうすれば、オブジェクトの位置を検索したいときはいつでも、オブジェクト内の位置フィールドを検索するだけで O(1) で実行できます。

ヒープ内の各値をヒープ内の位置にマップするヒープとともに、補助ハッシュ テーブルまたは BST を格納することもできます。これは最初のアプローチに似ていますが、間接的なレイヤーが追加されています。

お役に立てれば！

于 2012-12-11T17:20:40.353 に答える