問題
1つの優先度付きキュー（フィボナッチヒープ）に対して、以下の3種類のクエリを $Q$ 個、順番に処理せよ。
0 x: ヒープに整数 $x$ を1つ追加する。追加された要素には、挿入した順に $1,2,3,\dots$ という一意な管理番号（id）が割り当てられる。1: ヒープの最小値を出力し、その要素をヒープから取り除く。ヒープが空なら-1を出力する。2 id x: 管理番号idの要素の値を $x$ に減少させる。$x$ は現在値以下であることが保証される。idの要素はまだ抽出されていないことが保証される。
decrease-key（クエリ2）を償却 $O(1)$、extract-min（クエリ1）を償却 $O(\log Q)$ で処理する Fibonacci Heap を実装せよ。
入力形式
Q
query_1
...
query_Q制約
$1 \le Q \le 2\times10^5$
$0 \le x \le 10^9$
クエリ2の新値は現在値以下
クエリ2のidは未抽出の要素
入出力例
入力例1
8
0 5
0 3
0 8
1
2 3 1
1
1
1出力例1
3
1
5
-1入力例2
3
0 10
1
1出力例2
10
-1概念図
ヒント（段階的開示）
ヒント1（方向性）
二分ヒープの decrease-key は根への浮上が必要で $O(\log N)$。Dijkstra法の理論限界 $O(E+V\log V)$ を達成するには insert・decrease-key を償却 $O(1)$ にできる構造がいる。1本の木ではなく「木の森」として持ち、根同士を循環リストで束ねる発想はどうか。
ヒント2（アプローチ）
Fibonacci Heap は多分木の森。insertは新しい単一ノードの木を根リストに足すだけで$O(1)$。decrease-keyは親より小さくなったら部分木ごと根リストへ切り離す（cut）だけで$O(1)$。ただし無制限の切り離しは償却を崩すので、「1回切り離された印(mark)がある状態でさらに切り離されたら親も連鎖的に切り離す」ルールで制御する。extract-minのときだけ、同じ次数の根同士をまとめる consolidate が $O(\log N)$ 償却を生む。
ヒント3（誘導）
def cascading_cut(y):
z = parent[y]
if z != 0:
if not mark[y]:
mark[y] = True # 1回目は印だけ
else:
cut(y, z) # 2回目は連鎖的に切り離す
cascading_cut(z)extract-minでは子を全員根リストへ移し、その後 consolidate() で同じ次数の根同士をペアマージして木の本数を $O(\log N)$ 本に減らす。
模範解答 (Python)
import sys
def main():
data = sys.stdin.buffer.read().split()
idx = 0
Q = int(data[idx]); idx += 1
max_nodes = Q + 1
val = [0] * max_nodes
degree = [0] * max_nodes
parent = [0] * max_nodes
child = [0] * max_nodes
left = [0] * max_nodes
right = [0] * max_nodes
mark = [False] * max_nodes
min_node = 0
next_id = 0
def add_to_root_list(x):
nonlocal min_node
if min_node == 0:
left[x] = x
right[x] = x
min_node = x
else:
m = min_node
r = right[m]
right[m] = x
left[x] = m
right[x] = r
left[r] = x
if val[x] < val[m]:
min_node = x
def remove_from_list(x):
l = left[x]
r = right[x]
left[r] = l
right[l] = r
def insert(x_val):
nonlocal next_id
next_id += 1
nid = next_id
val[nid] = x_val
degree[nid] = 0
parent[nid] = 0
child[nid] = 0
mark[nid] = False
left[nid] = nid
right[nid] = nid
add_to_root_list(nid)
return nid
def merge_child_into(y, x):
parent[y] = x
if child[x] == 0:
child[x] = y
left[y] = y
right[y] = y
else:
c = child[x]
r = right[c]
right[c] = y
left[y] = c
right[y] = r
left[r] = y
degree[x] += 1
mark[y] = False
def consolidate():
nonlocal min_node
if min_node == 0:
return
roots = []
start = min_node
x = start
while True:
roots.append(x)
x = right[x]
if x == start:
break
DEG = 64
A = [0] * DEG
for x in roots:
d = degree[x]
cur = x
while A[d] != 0:
y = A[d]
if val[cur] > val[y]:
cur, y = y, cur
remove_from_list(y)
merge_child_into(y, cur)
A[d] = 0
d += 1
A[d] = cur
min_node = 0
for x in A:
if x != 0:
left[x] = x
right[x] = x
if min_node == 0:
min_node = x
else:
m = min_node
r = right[m]
right[m] = x
left[x] = m
right[x] = r
left[r] = x
if val[x] < val[m]:
min_node = x
def extract_min():
nonlocal min_node
z = min_node
if z == 0:
return None
zval = val[z]
if child[z] != 0:
c0 = child[z]
c = c0
children = []
while True:
children.append(c)
c = right[c]
if c == c0:
break
for c in children:
remove_from_list(c)
parent[c] = 0
add_to_root_list(c)
candidate = right[z]
remove_from_list(z)
if candidate == z:
min_node = 0
else:
min_node = candidate
consolidate()
return zval
def cut(x, y):
if right[x] == x:
child[y] = 0
else:
if child[y] == x:
child[y] = right[x]
remove_from_list(x)
degree[y] -= 1
add_to_root_list(x)
parent[x] = 0
mark[x] = False
def cascading_cut(y):
z = parent[y]
if z != 0:
if not mark[y]:
mark[y] = True
else:
cut(y, z)
cascading_cut(z)
def decrease_key(x, k):
nonlocal min_node
val[x] = k
y = parent[x]
if y != 0 and val[x] < val[y]:
cut(x, y)
cascading_cut(y)
if val[x] < val[min_node]:
min_node = x
out = []
for _ in range(Q):
t = int(data[idx]); idx += 1
if t == 0:
x = int(data[idx]); idx += 1
insert(x)
elif t == 1:
r = extract_min()
out.append("-1" if r is None else str(r))
else:
eid = int(data[idx]); idx += 1
x = int(data[idx]); idx += 1
decrease_key(eid, x)
print("\n".join(out))
main()Step-by-Step 解説
1「森」としてのヒープ表現
parent/child/left/right/degree/markの6配列で多分木の集合を表現。根同士、同じ親を持つ子同士がそれぞれ循環双方向リストになる。
parent/child/left/right/degree/markの6配列で多分木の集合を表現。根同士、同じ親を持つ子同士がそれぞれ循環双方向リストになる。
2insertは根リストへの挿入だけ
add_to_root_listはリンクリスト挿入なので$O(1)$。木の統合は行わずコストを先送りする。
add_to_root_listはリンクリスト挿入なので$O(1)$。木の統合は行わずコストを先送りする。
3decrease-keyはcutとcascading cut
markフラグで「1回目は印だけ、2回目は連鎖的に切り離す」ルールにより、1回のdecrease-keyが引き起こす切り離し回数を償却$O(1)$に抑える。
markフラグで「1回目は印だけ、2回目は連鎖的に切り離す」ルールにより、1回のdecrease-keyが引き起こす切り離し回数を償却$O(1)$に抑える。
4extract-minだけがコストを支払う
consolidateで同じ次数の根同士をマージし本数を$O(\log N)$本まで減らす。ここでそれまで先送りしたコストを回収する。
consolidateで同じ次数の根同士をマージし本数を$O(\log N)$本まで減らす。ここでそれまで先送りしたコストを回収する。
5償却解析の直感
ポテンシャル=木の本数+2×mark数。insert/decrease-keyは償却$O(1)$、extract-minは償却$O(\log N)$。
ポテンシャル=木の本数+2×mark数。insert/decrease-keyは償却$O(1)$、extract-minは償却$O(\log N)$。
よくあるミス
| ミス | 原因 | 正しい書き方 |
|---|---|---|
| cascading cutを無条件に再帰させる | markフラグの意味を理解せず毎回切り離す | markがFalseならTrueにして止める。Trueなら切り離して親へ再帰する |
| extract-minで「zが唯一の根だったか」の判定を誤る | 子を移した後に right[z] を見て混同する | remove_from_list(z)を呼ぶ直前にrigh[z]を候補として保存する |
| consolidateの次数テーブルサイズ不足 | 最大次数O(log_φN)を過小評価 | 安全側に大きめ（例:64）を確保する |
| decrease-keyで増加方向も許してしまう | increaseとdecreaseを区別せずヒープ順序を壊す | 新しい値が現在値以下であるという制約を前提にする |
| root list更新後min_nodeの更新漏れ | cut後に新しい最小値になるケースを見落とす | decrease_keyの最後で必ずval[x]<val[min_node]を確認 |
次のステップ
- 発展: 複数ヒープ間の「統合（union）」クエリをO(1)で処理する拡張（根リスト同士を繋げるだけ）。Skew Heap（Day136-Q1）との統合コストの違いを比較せよ。
- 発展2: Fibonacci Heapを用いたDijkstra法（O(E+V log V)）を実装し、二分ヒープ版（O(E log V)）と実測で速度比較せよ。密グラフ・疎グラフで結果がどう変わるか確認すること。