36

ヒープを使用して、要素がその中にあるかどうかをO（logN）時間計算量で検索できることを思い出しました。でもいきなり詳細がわからなくなってしまいました。getmindeleteaddなどしか見つかりません。

誰かがヒントを与えることができますか？

4

8 に答える 8

65

要素が内部にあるかどうかを判断するには、ヒープ内のすべての要素を検索する必要があります。

ただし、1つの最適化が可能です（ここでは最大ヒープを想定しています）。検索している要素よりも低い値のノードに到達した場合は、そのノードからさらに検索する必要はありません。ただし、この最適化を行っても、検索はO（N）のままです（平均してN / 2ノードをチェックする必要があります）。

于 2010-03-03T18:08:11.240 に答える
3

手遅れですが、ここでつまずく可能性のある人のためにこれを追加します。

ヒープ内の検索は、そのままではO（N）時間が必要になります。ただし、配列内のすべての要素を順番にポップアウトする1回の前処理のヒットを取得できる場合は、O（N.logN）でソートされた配列を取得します。事実上、ヒープソート。これで、ソートされた新しい配列をO（logN）時間で検索できます。

于 2019-07-29T15:18:43.850 に答える
3

ヒープの値にインデックスを追加すると、この問題を解決できます。Pythonでは、辞書を使用して実行できます。最小ヒープで操作を実行するたびに、ディクショナリ内のノードのインデックスを更新します。

これを実装する必要があるのは、最小ヒープの長さが非常に長く、最小ヒープを何度も検索する場合のみです。インデックスを追跡するためのコードには頭上が必要ですが、これによりプログラムの速度が少なくとも50〜60％向上します。

于 2019-10-02T14:57:05.647 に答える
2

他の人が述べているように、PriorityQueueでの検索は、ヒープのルート以外の特定のキーを探す場所の概念がないため、線形です。これは、検索する値に応じて常に左または右に移動することがわかっているBSTとの主な違いです。ヒープでは、最小のものは常にルートにあり、子は左または右のサブツリーに置くことができます。

ただし、PriorityQueueを変更して、インデックスkをヒープ配列内のその場所にマップする追加のインデックス配列を保持することができます。これにより、次の操作が可能になります。

void insert(int k, Item item)：アイテムを挿入してkに関連付けると、後でkから直接アクセスできるようになります。

Item get(k)：インデックスkに関連付けられているアイテムを返します。これは、ヒープ内のどこにあってもかまいません。

void change(int k, Item item)：kに関連付けられているアイテムをアイテムに変更します。これには、ヒープの順序が維持されるようにするための「再ヒープ化」が必要になります。

ヒープとインデックスの配列が常に同期し、正しいオブジェクトを指していることを確認する必要があるため、実装には多少注意が必要です。通常のヒープを実装する方法をすでに知っている場合は、インデックス配列を追加して、正しい順序を維持するために何を変更する必要があるかを確認してください。これが完全な実装ですhttps://algs4.cs.princeton.edu/24pq/IndexMinPQ.java.html

于 2020-09-04T17:15:20.407 に答える
1

あなたが探しているのはBST（二分探索木）だと思います。

于 2010-03-03T16:29:19.170 に答える
1

最悪の場合、ヒープ内の要素を見つけるための時間計算量は依然としてO（n）です。特定の要素を見つける必要がある場合は、O（logn）時間計算量の二分探索木を使用する必要があります

ヒープはmaxの検索/検索（O（1））に優れていますが、BSTはすべての検索（O（logN））に適しています。

于 2021-09-07T21:33:12.500 に答える
0

明確にするために、少し混乱しました。ヒープ（まだソートされていない）の場合、アイテムを検索する場合はO(n)、ソートされていない配列と同じように処理されますが、ヒープソートされている場合は、配列はすでにソートされているので、その場合、O(log n)アイテムを検索するのに（二分探索）かかります。

于 2021-05-10T10:04:18.063 に答える
0

ヒープでは、最高（または最低）の優先度要素が常にルートに格納されます。ただし、ヒープはソートされた構造ではありません。半順序と見なすことができます。

于 2021-12-14T20:06:35.307 に答える