引数ヒープ挿入

Question

のO（1）平均的ケースの複雑さのためにWikipedia page for binary heaps上の請求は、挿入は、最悪の場合にO（Nログ）が、平均でO（1）であることである。

必要な操作の数は、ヒーププロパティを満たすために新しい要素が増加する必要があるレベルの数にのみ依存します。したがって、挿入操作はO（ログn）の最悪ケースの複雑さを持ちますが、 O（1）。

次のようにこれを正当化するlinked page試み：

をしかし、平均的には、新たに挿入された要素が非常に遠く木まで移動しません。特に、キーの均一な分布を仮定すると、それはその親よりも大きい確率の半分を有する。それは親よりも大きいので、その祖父母よりも大きい機会が半分あります。それは親よりも大きいことを考えるとその曾祖父よりも大きい機会があり、そうすると[...]平均的な挿入には一定の時間がかかるようになる

これはしかし、確かにナンセンスですか？木が無作為に注文された場合、新しい要素が親よりも大きい確率は50/50になります。大まかに言えば、大きな要素が底に沈むので、ヒープが成長するにつれ、チャンスは50/50よりずっと小さくなります。

そうですか？

それは、数ヶ月のために、ウィキペディア上でそのようにされています...

Answer 1

平均時間ヒープ挿入がO（1）であるという主張のためのより良い参照があります：ヘイワード&マクダーミック1991年論文「Average Case Analysis of Heap Building by Repeated Insertionは」 。この論文では、Porter & Simonによる1975年の論文「ヒープへの単一の挿入を扱う "Random insertion into a priority queue structure"」を参照し、平均ケースがO（1）。

直感的には、引数は単純です。ヒープの半分は葉であり、葉はより大きくなる傾向があります。葉がヒープ内の最大の要素であると仮定すると、新しい要素が葉になる確率が上半分にあると言うことができます値の範囲の - は正確に0.5になります。新しい要素がヒープのリーフでない場合（確率0.5）、元のヒープ内の非リーフノードのみからなる切り詰めヒープでプロセスを繰り返すことができるため、新しい要素がセカンダリヒープにある確率は、最低レベルは残りの半分になります：0.25。したがって、それが第3レベルにある確率は0.125となります。次に、検索する必要のあるレベルの数は、1 * 0.5 + 2 * 0.25 + 3 * 0.125 ... 2となります。

もちろん、ランダムな新しい要素がランダムな第2レベルの親は実際には0.5ではありません。それは実際には少し少ないです。しかし、定数で囲まれている限り、と予想されるの数を計算するべき級数の和は、やはり定数で囲まれます。そして定数は約2.6であることが判明しました。

this useful answerも参照してください。