0

私の質問は次のとおりです。

トリプルのリストが与えられ、それらは hash_heap と呼ばれるデータ構造に格納されます (名前についてはわかりませんが、ハッシュテーブルとヒープが混在している必要があります)。そして、データ構造が次のメソッドを提供することを願っています。

index_by_first_col(key) // the method could help find the a triple stored in it by matching the first column. It expects the searching is running at constant time
get_min_by_third_col() // the method get the minimum triple sort according to the third column, it is also expects the method is running at constant time.
insert_new_elt(triple) // add new trip, running at constant time

このようなデータ構造を実装することは可能ですか? ハッシュテーブルが最初の方法をサポートし、ヒープが 2 番目と 3 番目の方法をサポートできることは知っていますが、それらを組み合わせる方法がわかりません。何か案は？

ありがとう！

4

1 に答える 1

1

記載された要件を満たす非常に単純なデータ構造があります。

ハッシュ テーブル (最初の列をキーとする) を使用し、さらに最小要素へのポインターを (3 番目の列で) 格納します。次に、index_by_first_colはハッシュテーブル ルックアップ、get_min_by_third_colはポインタ デリファレンス、insert_new_eltはハッシュ テーブルの挿入と比較で、最小ポインタを更新する必要があるかどうかを判断します。

これにより、(最小の) O(n) の削除が行われることに注意してください。ただし、削除に関する要件は述べていません。

于 2011-01-10T20:06:40.520 に答える