二分ヒープへの挿入
- 葉に追加した後、制約を満たすまで親とスワップする必要がある
- 最悪で木の高さ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なので、繰り上がり操作の回数の平均は定数オーダーになる