ビープ

ビープ（または双親ヒープ）は、セット（またはマップ、マルチセット、マルチマップ）のデータ構造であり、要素（またはマッピング）を準線形時間で検索、挿入、削除することを可能にします。ビープでは、各要素は最大2つの親ノードと最大2つの子ノードを持つノードに格納され、親ノードの値はどちらの子ノードの値よりも大きくなることはありません。

ビープは、格納する値のみを含む配列を使用して実装され、親子関係は配列のインデックスによって暗黙的に決定されます。（つまり、ビープは暗黙的なデータ構造です。）この点では、通常同様の方法で実装されるバイナリヒープと似ています。ただし、ビープのパフォーマンス特性はヒープとは異なり、特に、任意の要素を準線形時間で取得できます。

ビープはイアン・マンローとヘンドラ・スワンダによって導入された。関連するデータ構造としてヤングタブローがある。

構造物の高さは約${\displaystyle {\sqrt {n}}}$また、最後のレベルが満杯だと仮定すると、そのレベルの要素の数も${\displaystyle {\sqrt {n}}}$実際、これらの特性により、すべての基本操作（挿入、削除、検索）は${\displaystyle O({\sqrt {n}})}$平均時間。ヒープ内の検索操作は${\displaystyle O(n)}$最悪の場合。新しい要素の削除と挿入には、beap 不変条件を復元するために要素を上下に伝播させる必要があります (ヒープの場合とよく似ています)。さらに、beap は最小要素への定数時間アクセスを提供し、${\displaystyle O({\sqrt {n}})}$最大要素の時間。

実際、${\displaystyle O({\sqrt {n}})}$各ノードに親ポインタが保持されていれば、検索操作を実装できます。最上位ノードの最下位要素（ヒープの最左端の子ノードに相当）から開始し、上方向または右方向に移動して目的の要素を探します。

• Munro, J. Ian; Suwanda, Hendra (1980). "高速検索と更新のための暗黙的データ構造" . Journal of Computer and System Sciences . 21 (2): 236–250 . doi : 10.1016/0022-0000(80)90037-9 .
• Williams, JWJ (1964年6月). 「アルゴリズム232 - ヒープソート」. Communications of the ACM . 7 (6): 347–348 . doi : 10.1145/512274.512284 .