設問とコンテキスト
タスクスケジューラ用のマージ可能な最小優先度付きキュー（min-priority queue）を実装しています。呼び出し側は頻繁に2つのキューを結合し、ワークを挿入して最小の優先度を取り出します。meld、insert、find-min、および extract-min を実装し、ランダム化、空のヒープ、重複キー、およびノードの所有権に関する設計選択を述べてください。
ランダム化マージ可能ヒープは、左性ヒープのランク（leftist rank）のようなランクメタデータを持たない二分木としてヒープ順序を表現します。各マージにおいて、左または右の再帰ブランチをランダムに選択します。この面接では、不変条件、確率の前提条件、およびテスト容易性が評価されます。
面接官が評価するポイント
最小ルート不変条件、meld の交換および消費セマンティクス、ランダムビットの境界、重複キー、所有権、再帰の深さ、破棄、そして期待計算量と最悪ケース境界の違いを網羅してください。ワークロードに応じて二分ヒープ、左性ヒープ、ペアリングヒープを比較します。
行うべき確認の質問
meldは入力ヒープを消費しますか、それとも両方の元のヒープを使用可能なまま維持する必要がありますか？- 障害を再現できるようにランダムソースを注入（inject）できますか？
- ノード数の上限と再帰スタックのバジェットはどのくらいですか？
- 安定したハンドル、任意の削除、または
decrease-keyは必要ですか？ - 目的は教育用の実装、本番環境向けのスループット、それとも厳密な最悪ケースの計算量保証ですか？
30秒の回答フレームワーク
「各ノードはキー、値、および2つの子ポインタを保持します。meld(a,b) は空のツリーを処理し、小さい方のルートを保持した上で、もう一方のツリーを左右どちらかの子にランダムにマージします。insert は単一ノードをルートとマージし、extract-min は削除されたルートの子同士をマージします。ルートは常に最小を維持し、操作は一般に期待対数時間になりますが、再帰の深さと乱数シードには明示的なテストと制限が必要です。」
ステップ別の詳細な回答
ステップ 1: ノードと所有権を定義する
各ノードに key、value、left、および right を格納します。ヒープはそのルートとノード数を保持します。可変（mutable）な実装では、meld が入力ルートを再接続するため、APIは入力が消費されるかどうかを明示すべきです。永続（persistent）実装ではパスをコピーするため、時間と空間のコストが変化します。
meld(a, b):
if a is empty: return b
if b is empty: return a
if b.key < a.key: swap(a, b)
if randomBit() == 0:
a.left = meld(a.left, b)
else:
a.right = meld(a.right, b)
return aステップ 2: マージ不変条件を維持する
最初にルート同士を比較し、小さい方のキーをルートとして維持します。等しいキーには固定のタイブレークルールまたはランダムルールを使用できますが、ヒープ順序は有効でなければなりません。再帰が戻った後、マージされた子内のすべてのキーは現在のルート以上になるため、パスに沿って不変条件が保持されます。
1つのノードを2つの親に接続してはいけません。可変の meld は所有権を追跡すべきであり、デバッグビルドではカウントと循環参照をチェックできます。永続実装では共有サブツリーを変更することはできません。
ステップ 3: Insert と Find-Min を実装する
insert は単一ノードを作成して現在のルートとマージし、カウントをインクリメントします。find-min はルートを読み取ります。空のヒープは空の結果またはエラーを返すことでインターフェースの契約に従います。重複キーは別個のエントリとして維持されます。
グローバルなランダムソースを使用すると、テストの再現が困難になります。ランダムソースを注入し、テストでは固定シードを使用します。本番環境では依然として偏りのない独立したランダムビット実装が必要です。
ステップ 4: Extract-Min を実装する
ルートを削除した後、その左右のサブツリーをマージして新しいルートを形成します。カウントをデクリメントする前に両方のポインタを切り離します。ヒープがメモリを所有している場合は、最後に古いルートを解放します。入力が消費される場合は、削除されたルートへのハンドルを無効化します。
古いバージョンを使用可能なまま維持する必要がある場合は、共有ノードを変更する代わりに永続パスコピーを使用してください。エイリアシングによってデータが暗黙的に破損する可能性があるため、これをインターフェース境界で明示してください。
ステップ 5: 計算量の境界を明示する
ランダム化マージ可能ヒープの場合、meld、insert、および extract-min は、明記されたランダムモデルの下で期待対数時間または高確率対数時間として一般に解析されます。find-min は定数時間であり、空間計算量はノード数に対して線形です。
期待計算量を操作ごとの最悪ケースの主張にすり替えてはいけません。不運なランダムシーケンスによって深いツリーが生成される可能性があります。本番コードでは再帰を制限し、必要に応じて明示的なスタックを使用し、ベンチマークとランダムテストで分布を検証する必要があります。
ステップ 6: 参照実装に対してテストする
空のヒープ、重複キー、交互のマージ、繰り返しの取り出し、固定シード、深さの極端なケースを用いて、標準の優先度付きキューに対して差分テストを実行します。各操作の後に、最小ルート、ノード数、非巡回性、および所有権ルールをチェックします。
ペアリングヒープとは異なり、この設計は二分木とランダム分岐を使用するため、兄弟リスト、2パスマージ、ハンドルの切り離しは不要です。左性ヒープとは異なり、ランクメタデータを省略して確率的解析を使用します。キャッシュ局所性、変更可能性、および証明要件を総合して議論してください。
質の高い模範解答
最小のキーをルートに保持します。meld は空でないツリーを返し、a が小さくなるようにルートを入れ替え、b を a.left または a.right にランダムにマージします。insert と extract-min は両方とも meld を再利用し、find-min はルートを読み取ります。まず meld が入力を消費するかどうかを確認し、差分テスト用に決定論的なランダムソースを注入して、循環、カウント、所有権、ルートの順序をチェックします。ランダムモデルにおける期待または高確率対数境界を説明し、再帰の深さは別途処理します。
よくある間違い
- ルートを比較する前にランダム化する → 結果のルートが大きくなりすぎる可能性がある → 先にルートを入れ替えてから子を選択する。
- meld の後に古い可変ヒープを再利用する → ノードが2つの親を持つことになる → 消費を明示するか永続性を実装する。
- 期待境界を最悪ケースの O(log n) と呼ぶ → 確率の前提条件が失われる → ランダムモデルと高確率の修飾子を明記する。
- 注入不可能なランダムソースを使用する → 障害を再現できなくなる → 注入可能にしてテストでシードを固定する。
- 再帰の深さを無視する → 極端なツリーによりコールスタックが枯渇する可能性がある → 明示的なスタックを使用するか、深さを監視するか、制限を文書化する。
フォローアップの質問と回答
フォローアップ 1: テストを決定論的にするにはどうすればよいですか？
ランダムビットジェネレータをヒープの依存関係として注入できるようにします。グローバルなランダム状態がテストケース間で干渉しないよう、テストでは固定のシーケンスまたはシードを提供し、本番環境では独立したインスタンスを使用します。
フォローアップ 2: meld が両方の入力を保持しなければならない場合はどうしますか？
パスコピーと変更されていないサブツリーの共有を行う永続実装を使用します。空間計算量とメモリ解放計画を更新し、インプレースマージに対して定数の追加空間を主張しないようにします。
フォローアップ 3: 両方のヒープが同じノードを参照している場合はどうなりますか？
可変 API ではヒープ間のノード共有を拒否し、デバッグビルドで所有権を記録する必要があります。永続 API では、ノードが不変である場合にのみ構造を共有できます。エイリアスを暗黙的に修復するのではなく、所有権エラーを返します。
フォローアップ 4: なぜペアリングヒープを使用しないのですか？
ペアリングヒープは decrease-key を必要とするワークロードに適していますが、多分木の子リストと削除時の再構築を管理します。ランダム化マージ可能ヒープは、確率的保証を受け入れつつ、マージ、挿入、最小値の削除を必要とするワークロードに対して、よりシンプルな二分の meld を備えています。