二分ヒープの挿入が平均定数時間

葉に追加した後、制約を満たすまで親とスワップする必要がある

最悪で木の高さO(logN)

しかし深さnの頂点が2^n個であることから？

親と交換しなければいけない確率が

(進むたびに？)1/2になるので、

平均値を求めると定数になる？

ちょっと怪しい

The average cost of inserting n elements into an initially empty heap is analyzed, under the assumption that the n! orders in which the n elements can be inserted are equally likely. It is proved that this average, expressed in number of exchanges per insertion, is bounded by a constant about 1.7645.

同様の理由で繰り上がりが必要になる確率が1/2なので、繰り上がり操作の回数の平均は定数オーダーになる