<a href="/ja/%E4%BA%8C%E5%88%86%E3%83%92%E3%83%BC%E3%83%97">二分ヒープ</a>への挿入
<ul>
<li>葉に追加した後、制約を満たすまで親とスワップする必要がある</li>
<li>最悪で木の高さO(logN)</li>
<li>しかし深さnの頂点が2^n個であることから？<ul>
<li>親と交換しなければいけない確率が</li>
<li>(進むたびに？)1/2になるので、</li>
<li>平均値を求めると定数になる？</li>
</ul>
</li>
<li>ちょっと怪しい</li>
<li><blockquote>
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.
</blockquote>
<ul>
<li><a href="https://www.sciencedirect.com/science/article/abs/pii/0196677485900288">https://www.sciencedirect.com/science/article/abs/pii/0196677485900288</a></li>
</ul>
</li>
</ul>
<a href="/ja/%E4%BA%8C%E9%A0%85%E3%83%92%E3%83%BC%E3%83%97">二項ヒープ</a>への一要素のマージ
<ul>
<li>同様の理由で繰り上がりが必要になる確率が1/2なので、繰り上がり操作の回数の平均は定数オーダーになる</li>
</ul>

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