[過去ﾛｸﾞ] 競技プログラミングにハマるプログラマのスレ 227 (1002ﾚｽ)
上下前次1-新
このｽﾚｯﾄﾞは過去ﾛｸﾞ倉庫に格納されています｡
次ｽﾚ検索 歴削→次ｽﾚ 栞削→次ｽﾚ 過去ﾛｸﾞﾒﾆｭｰ
259: 05/22(木)02:20 AAS
はい、承知いたしました。Skew Heapの償却O(log n)解析（RightHeavyノードをポテンシャルとして使用）を記述します。
Skew Heapの償却O(log n)解析 (RightHeavyポテンシャル)
1. 定義
- 部分木のサイズ size(x): ノード x を根とする部分木に含まれるノードの総数。
- 左の子 lc(x)、右の子 rc(x): ノード x のそれぞれ左の子、右の子。
- RightHeavyノード: ノード x が右の子 rc(x) を持ち、かつ size(rc(x)) > size(lc(x)) である場合、ノード x は RightHeavy であると定義します。（左の子がない場合は size(lc(x))=0 とします。）
- ポテンシャル関数 Φ(H): ヒープ H に含まれるRightHeavyノードの総数。
省6
上下前次1-新書関写板覧索設栞歴
あと 743 ﾚｽあります
ｽﾚ情報 赤ﾚｽ抽出 画像ﾚｽ抽出 歴の未読ｽﾚ AAｻﾑﾈｲﾙ
ぬこの手 ぬこTOP 0.014s