[過去ﾛｸﾞ] 競技プログラミングにハマるプログラマのスレ 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ノードの総数。

2. Meld操作の償却解析

Skew Heapの主な操作である meld(H1, H2) について考えます。簡単のため、H1 の根のキーが H2 の根のキー以下であると仮定します（そうでない場合は H1 と H2 を交換します）。H1 の根を x_0 とします。

Meld操作は、x_0 から始まる右パス P = (x_0, x_1, ..., x_k) に沿って再帰的に処理を行います。各ノード x_i (0 <= i <= k) において、以下の処理が行われます：
1) x_i の元の右の子 R_i (= x_{i+1} または H2 の一部) と、H2 の残り（または R_i が H2 そのものの場合もある）を再帰的にmeldし、その結果を x_i の新しい右の子 R'_i とします。
2) x_i の元々の左の子 L_i と、新しい右の子 R'_i をスワップします。つまり、meld後の x_i の左の子は R'_i、右の子は L_i となります。

このパスの長さ（スワップが行われる回数）を m=k+1 とすると、meld操作の実際のコスト C は O(m) です。

---

上下前次1-新書関写板覧索設栞歴

---

あと 743 ﾚｽあります
ｽﾚ情報 赤ﾚｽ抽出 画像ﾚｽ抽出 歴の未読ｽﾚ AAｻﾑﾈｲﾙ

---

ぬこの手 ぬこTOP 0.009s