バイナリヒープO（1）に挿入する平均的なケースはなぜですか？

Question

ヒープの整合性を維持するためにpercDown値を使用する必要があるため、削除の平均ケースがlg（n）の場合、ヒープの挿入とpercUpingで同じではないのはなぜですか？入力（n）に比例して2で割った比較の量ではありませんか？

Answer 1

これは興味深い提案です。私は基本的な計算をしようとしました。計算がバグであるかどうか見てください。これは、基本的に、いくつかの仮定を伴う機械的計算です。

と仮定：

1. が2^k-1要素の完全なバイナリツリー内のkレベルが既に存在しています。
2. 2^kツリーに追加する要素を追加すると、レベルがになります。
3. 要素は、均一かつランダムに（3）古い木の各要素は、本質的に新しい要素に置き換えられていることを示し[1..k]

からレベルに位置し得ます。したがってpercolationsの数が上向きになります。

k + 2 * (k-1) + 4 * (k - 2) + ... + 2^(k-1) * 1 
= k + 2 * k + 4 * k + ... + 2^(k-1) * k - (2 + 2 * 2^2 + 3 * 2^3 + ... + (k - 1) * 2^(k-1)) 
= k * (2 + 4 + ... + 2^(k-1)) - (k * 2^k - 2 * (2^k - 1)) ......(a) 
= k * (2^k - 1) - k * 2^k + 2 ^(k+1) - 2 
= k * 2^k - k - k * 2^k + 2^(k+1) - 2 
= 2^(k+1) - (k + 2) 

（A）here計算されます。

2^kしたがって、(2^(k+1) - (k+1) - 1)ステップを使用してパーコレートされた要素があります。したがって、平均コストはO((2^(k+1) - (k+1) - 1)/2^k) = O(2 - (k+2)/2^k)であり、O(1)です。

したがって、一定の挿入コストを想定することができます。

注：我々は要素が確率0.5に置き換えられてしまいますと仮定した場合、我々は、上記の計算にそれを織り込むことができ、私はそれが1に近くなってきて分裂につながることをを考える。

Answer 2

ヒープの挿入とパーックアップで同じではないのはなぜですか？

ヘッド（h）を削除すると、最も長いサブツリーの最も低い要素（l）であるヒープの最後の要素に置き換えられます。 lをより高いレベルのヒープに入れる確率は、それが既にそのサブツリーの最も低い要素であるので、無視できるほど十分に低いと考えられます。

特別なケースがあります。たとえば、N個の等しい整数を含むヒープは、O（1）でヘッド抽出を行います。しかし、一般的なケースではありません。

Answer 3

私はバイナリヒープについて学び始めたとき、まったく同じことを思っていました。私はC言語の実装を書いていましたが、私はさまざまな操作をタイムアウトしたときにこの現象に困惑しました。それを考えた後の私の直感は、他の誰かが言及したように、要素を削除すると、ヒープ内のその部分が最後の要素、すなわち底に属する要素に置き換えられます。したがって、下に沈む。私のテストでは、ヒープの先頭要素の削除を試みただけなので、これらの削除は常にヒープ全体の高さ（log n）のトラバーサルにつながります。一方、

挿入は、一番下に新しい要素を置き、それが浮上することができます。これは、ヒープの要素のほとんどは低いレベルに集中しているので、新しいノードは、それが1つまたは2つのジャンプで正しい位置だ達している可能性があるというのが私の考えです。ノードの値がヒープ全体の平均値であっても、通常、ヒープの垂直中間レベルまでジャンプする必要はありません（2^x要素を含むヒープの最下位レベルヒープ全体のノードの半分以上が1つ含まれています）。それが理にかなっているかどうかはわかりませんが、それは私にはあります:)。

除去することによって、我々はただ、トップ1を任意の要素を削除していない話をしている場合今、私は表示されない理由は平均的なケースがO（1）すぎ、以来、我々は可能性が最も高いであるべきではありません下の方に何か...