検索はバイナリヒープ操作ですか？

Question

による ウィキペディアページ, 、検索はバイナリヒープの「操作ではない」です（右上の複雑さボックスを参照）。

なぜだめですか？バイナリヒープはソートされない場合がありますが、それらは順序付けられており、完全なグラフトラバーサルは$ o（n）$ timeで任意のオブジェクトを見つけることができますか？

ページは間違っていますか、それとも私ですか？

Answer 1

実際、それはあなたの視点、または詳細レベルに依存します。

ヒープ, 、またはより良い 優先キュー, 、抽象データ構造は通常、のような操作をサポートしているためです Is-Empty, アドレスのエレメント, 削除 - マン. 。通常はそうではありません 発見要素. 。これは、仕様として見られるデータ構造であり、一連の操作とその動作を修正します。実装は不明であり、リンクされたツリーまたは配列にすることができます。

ただし、ウィキペディアページは実装に関係しています。それはタイトルからも明らかです バイナリヒープ. 。 （バイナリヒープがツリーであるかのように見えることで理解し、配列を使用して実装します）。この実装では、操作をプログラムする方法が簡単にわかります 発見要素. 。技術的には、これは別の抽象データ構造です（標準のヒープ操作からの追加の操作APRTがあるため）。

実際には、Heaps（優先キュー）がDijkstraのようなグラフアルゴリズムによく使用されます。ヒープに保存されている優先順位を変更できることが重要です（短いルートが見つかった場合）。これは、ヒープ内の要素を見つけることができ、その優先度を調整できる（そしてヒープ内の要素を再配置する）ことができる場合にのみ可能です。通常、これはヒープの上に別の構造を構築することによって行われ、要素が保存されている位置を効率的に見つけることができます。

Answer 2

バイナリヒープでは、値が実際に順序付けられ、値/キーが配列の最後の値である場合、検索操作は配列のスキャンに縮退します。ただし、検索している値が最初の値（つまり、0に近いインデックス）に近い場合、早めに停止し、そこにない値を探して配列をスキャンしないことができます。

たとえば（C ++）、バイナリヒープを保持するベクトルのこのような実装：

template <class Compare>
uint32_t SearchHeapImpl(const uint32_t idx, const T V, const Compare &cmp) const
{       
    if (slots[idx] == V)
        return idx;
     else if (cmp(slots[idx], V))
         return UINT32_MAX;

     const auto leftChild = 2 * idx + 1;

     if (leftChild >= nElements)
         return UINT32_MAX;

     const auto i = SearchHeapImpl(leftChild, V, cmp);

     if (i != UINT32_MAX)
         return i;

     const auto rightChild = leftChild + 1;

     return rightChild >= nElements ? UINT32_MAX : SearchHeapImpl(rightChild, V, cmp);
}

template<class Compare = std::greater<T>>
uint32_t SearchHeap(const T V, const Compare cmp = Compare()) const
{
    return nElements ? SearchHeapImpl(0, V, cmp) : UINT32_MAX;
}

早めに検索を中止します cmp(slots[idx], V) == true

他の人が述べたように、そのようなデータ構造はO（1）Peek、およびO（log n）挿入および削除操作に適しています。スキップリストまたはセルフバランスのバイナリツリー（赤い黒い木など）は、通常、O（log n）検索が必要な場合はより良い代替手段です（o（1）、o（1）、o（log n）for searchのためにo（1）を交換します）。もちろん、それらは通常より複雑で、より多くのメモリを必要とし、ランダムアクセスパターンはキャッシュヒットミスなどのためにパフォーマンスに影響を与える可能性があります。