2

追跡する（キー、値）オブジェクトがたくさんあり、多くの挿入と削除があるとします。

次の3つの要件を満たす必要があります。

  1. 任意の時点で一定時間内に最大キーを取得します
  2. 対数時間で任意のキーの値を検索します。
  3. 挿入と削除には対数時間がかかります。

これを行うことができるデータ構造はありますか？

私の考え：

優先キューは一定時間で最大値を取得できますが、値を検索できません。二分探索木（2〜3木）は対数時間で検索できますが、maxもO（lgN）を取ります。BSTで最大値を追跡しようとすると、最大値を削除して2番目に大きいものを見つける必要があるときにO（lgN）がかかります。

4

9 に答える 9

10

なぜこれらの凝ったデータ構造体が必要なのでしょうか? Max ノードを追跡する単純な二分探索ツリーは、OP の要件を十分に満たすことができると思います。

  1. 最大キーでノードを追跡できます。

    新しいノードを挿入するたびに、キーを以前の最大キーと比較して、これが新しい最大ノードであるかどうかを判断します

    最大ノードを削除するたびに、次の最大ノードを見つけるのに O(logN) かかります

  2. BST の性質上、O(logN) ルックアップ時間は確かにあります

  3. BST の更新には O(logN) 時間がかかります

于 2012-06-14T18:22:36.107 に答える
4

2つのデータ構造を並行して使用できます-

  1. キーと値のペアをハッシュ テーブルまたはバランスの取れた BST に格納して、O(log n) ルックアップを取得します。
  2. O(1) 時間で最大値を検索できるように、すべての値を最大ヒープに格納します。

これにより、挿入または削除に O(log n) 時間がかかります。これは、最大ヒープからの挿入または削除の複雑な時間であるためです。

お役に立てれば！

于 2012-06-14T17:45:12.390 に答える
3

スキップリストには償却されたO(logn)ルックアップがあり、それらはリンクされたリストであるためmin、max常にO(1)です。http://en.wikipedia.org/wiki/Skip_list

于 2012-06-14T17:53:25.270 に答える
1

キーと値のペアを使用しているため、JavaでTreeMapを使用することをお勧めします。

Treemapにある次の 4 つのメソッドを簡単に使用できます。

  • 挿入および取得のための get() および put(key,value) メソッド
  • 最大キーを見つけるための lastKey()。
  • remove(key) で削除。

または、このページのように次の構造を使用します

最終的な結論:

スペースの複雑さをトレードオフし、実行時間を重視する場合は、2 つのデータ構造が必要です。

挿入、取得、および削除に O(1) を持つ HashMap または TreeMap を使用します。

次に、2番目のリンクに従って、2つのスタックデータ構造を使用してo(1)の最大値または最小値を見つけます。

これが私ができる最善の解決策だと思います。

于 2012-06-15T07:29:58.437 に答える
1

降順でソートされたリストはどうですか？

  1. Max は常に最初なので、O(1) です。
  2. ルックアップは、二分探索による O(log n) です。
  3. n-i位置iから挿入/削除するときにアイテムをシフトする必要があるため、挿入/削除はO(n)です。
于 2012-06-14T17:53:16.757 に答える
1

キーを使用し、その値を即座に検索できるという事実により、ハッシュテーブルの検索時間は O(1) であることはわかっています。最大値に関しては、値を挿入または削除するたびに常に追跡できる場合があります。

于 2012-06-14T17:45:34.497 に答える
0

RMQ (Range minimum-maximum Query) データ構造またはセグメント ツリーデータ構造を見てください。どちらも O(1) クエリ時間がありますが、値を格納するために何らかの方法で変更する必要があります..

ここに素晴らしい記事があります http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=lowestCommonAncestor

于 2012-06-14T17:48:28.960 に答える
0

ツリー データ構造の削除は既に O(logN) 操作であるため、2 番目に大きいキーを探しても操作の複雑さは変わりません。

ただし、要素を削除する代わりに無効にすることはできます。また、データ構造内にポインターを保持しておくと、最大のものから 2 番目に大きいものへの移動は O(N) 操作になる可能性があります。

于 2012-06-15T08:22:05.313 に答える
0

最初のコメントが言うように、max heapを使用してください。ハッシュマップを使用してポインターをヒープに格納します。これらは、一定時間のルックアップとログ時間の削除に使用されます。

ヒープの実装は非常に簡単です。BST のようにバランスをとる必要はありません。ハッシュマップは通常、選択した言語に組み込まれています。

于 2012-06-14T21:30:08.697 に答える