二分ヒープの挿入が平均定数時間
二分ヒープへの挿入
葉に追加した後、制約を満たすまで親とスワップする必要がある
最悪で木の高さ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なので、繰り上がり操作の回数の平均は定数オーダーになる
Related Pages
- →二分ヒープ×データ構造×ヒープキュー×優先度キュー×priority_queue×ある集合に値が追加削除される。最小の値を取得したい。×m個の数がn個の集合を移動する。集合の最小要素を得たい×n個の値が更新される、最小値を知りたい×ヒープのk番目の値を更新したい×中央値×best_kの取得→
"Engineer's way of creating knowledge" the English version of my book is now available on [Engineer's way of creating knowledge]
(C)NISHIO Hirokazu / Converted from [Scrapbox] at [Edit]