プロンプトとコンテキスト
タスクの優先度を下げることができるイベントスケジューラ向けに、マージ可能な最小優先度付きキュー（meldable min-priority queue）を実装します。二分ヒープ（binary heap）でも基本操作は処理できますが、meld と decrease-key にはコストがかかります。ハンドル、リンク、2 パス結合、削除、およびエッジケースを備えたペアリングヒープを実装してください。
ペアリングヒープは、シンプルな実装と実用的な優れたパフォーマンスを両立させることを目的とした自己調整型ヒープとして 1986 年に導入されました。元の論文では部分的な計算量解析しか示されていませんでした。この面接では、コードの正確性、ならし計算量の推論、および証明されていない計算量の主張を明確に区別できているかが試されます。
面接官が評価するポイント
最小ヒープ不変条件、定数時間の meld、2 パスによる兄弟ペアリング、無効なハンドル（stale handle）、cut-and-relink による decrease-key、空キーや重複キーの扱い、メモリの所有権、そして二分ヒープやフィボナッチヒープとのトレードオフについて網羅してください。
確認すべき明確化のための質問
- decrease-key は必須ですか、それとも push/pop のみで十分ですか？また、操作の比率はどのようなものですか？
- ノードのハンドルは安定している（不変である）必要がありますか？また、無効なハンドルはどのように検出しますか？
- 再帰は許可されていますか？最大ヒープサイズとスタック予算はどのくらいですか？
- コンパレータが例外を送出したり変更されたりする可能性はありますか？また、重複する優先度はサポートしますか？
- 目標は教育的な明快さ、小さな定数倍による実用的な速度、または厳密な最悪計算量の証明のどれですか？
30秒で答える要約
「各ノードにはキー、ペイロード、親、最初の子、次の兄弟を格納し、ハンドルはそのノードを指します。Link は 2 つのルートを比較し、キーが大きい方のルートを小さい方のルートの最初の子にします。Delete-min はルートを切り離し、兄弟を左から右へペアでリンクした後、右から左へとマージします。Decrease-key は非ルートノードを切り離し、ルートとしてマージ（meld）します。ハンドルの状態を追跡し、ならし解析と確立された解析を用いて計算量を説明します。」
ステップごとの詳細解説
ステップ 1: ノードとハンドルの定義
各ノードにキー、ペイロード、親、最初の子、および右の兄弟を格納します。ハンドルはノードを指し、有効フラグ（live marker）や世代情報を保持することで、削除後の decrease-key を防ぎます。ルートには親がなく、兄弟リストの末尾は null です。
Node { key, value, parent, firstChild, nextSibling, alive }
Heap { root, size }コンパレータは値の順序付けのみを行い、ノードを変更してはなりません。等しいキーは別々のノードとして扱い、要求される安定性ポリシーを適用します。
ステップ 2: link と meld の実装
link(a, b) は 2 つのルートを比較し、キーが大きい方のルートを小さい方のルートの最初の子とし、親ポインタと兄弟ポインタを更新します。meld は 2 つのルートをリンクするだけです。一方が空のヒープの場合はもう一方のルートを返します。
ポインタ更新のたびに、ルートに親がないこと、各子が親を指し戻していること、そしてサイズが変化していないことをアサートします。デバッグビルドでは構造体を走査して循環参照をチェックできますが、本番環境の操作で毎回線形チェックを実行すべきではありません。
ステップ 3: insert と find-min の実装
insert は単一要素のヒープを作成し、それをルートとマージ（meld）して、安定したハンドルを返します。find-min はルートを読み取ります。空のヒープの場合は、null の逆参照を行うのではなく、API の空結果またはエラーを返します。
呼び出し側がハンドルを保持する場合、ヒープの移動や拡張によってハンドルが無効化されてはなりません。ノードを個別に割り当てるか、安定した間接参照層を使用し、ヒープがノードを所有するのかペイロードのみを所有するのかを文書化してください。
ステップ 4: 2 パス delete-min の実装
ルートを削除した後、その子リストを切り離してルートリストにします。第 1 パスでは、隣接するルートを左から右へペアでリンクします。要素数が奇数の場合は最後のルートをそのまま保持します。第 2 パスでは、その結果を右から左へマージ（meld）します。
deleteMin(h):
children = detachChildren(h.root)
pairs = linkAdjacent(children)
newRoot = mergeRightToLeft(pairs)
invalidate(h.root)
h.root = newRoot
h.size -= 1マージ処理中に古い親ポインタと兄弟ポインタをクリアし、削除されたルートが保持されないようにします。長い兄弟チェーンによるスタックオーバーフローを回避するために、反復的なリスト処理を使用してください。
ステップ 5: decrease-key の実装
小さくなっていない新しいキーは拒否するか、別の increase-key 操作を定義します。ルートの場合はキーのみを更新します。非ルートノードの場合は、親の子リストから切り離し、兄弟ポインタを修復して、独立したルートとしてマージ（meld）します。
切り離しには前の兄弟が必要です。親のリストを走査するか、prevSibling ポインタを追加してメンテナンスコストの増加を受け入れます。無効なハンドル、別のヒープのノード、または破棄されたヒープに対してはエラーを返します。
ステップ 6: 不変条件と計算量のテスト
重複キー、空ヒープ、連続した decrease-key、全ノードの削除、ランダムな meld を網羅し、標準の優先度付きキューに対するランダム差分テストを使用します。各操作の後に、ルートが最小であること、サイズが生存ノード数と一致すること、および親子リンクが非巡回であることを検証します。
証明された境界、ならし解析の直感、および測定値を明確に区別してください。ペアリングヒープの insert と meld は定数倍が小さいですが、delete-min や decrease-key の厳密な解析が存在するからといって、すべての操作が最悪ケースで O(log n) であると主張してよいわけではありません。前提条件を明記し、二分ヒープやフィボナッチヒープと比較してください。
優れた回答例
私なら、link、meld、2 パス delete-min、および decrease-key のために、親、最初の子、次の兄弟ポインタ、そして安定したハンドルを使用します。非ルートの decrease-key では、新しいルートとしてマージされる前に兄弟リストから切り離されます。delete-min は左から右へペアリングし、右から左へマージします。標準の優先度付きキューに対する差分テストを行い、非巡回性とサイズの不変条件を検証し、ならし解析、最悪ケースの境界、および実践的なベンチマークを区別して説明します。
よくある間違い
- キーのみを変更する → ヒープ順序と親リンクが壊れる → 非ルートの decrease-key はすべて切り離して meld する。
- 2 つのパスクの順序を逆にする → 形状と結果が正しくなくなる → 左から右へペアリングし、次に右から左へマージする。
- 削除されたハンドルを使用する → use-after-free やヒープ間の不正変更が発生する → 無効化を行い所有権を検証する。
- すべての操作が最悪ケースで O(log n) だと主張する → その計算量には裏付けがない → ならし計算量、部分的な解析、および実測値を区別する。
- 長い兄弟リストを再帰処理する → スタックオーバーフロー → 反復リスト処理を使用する。
フォローアップ質問と回答
フォローアップ 1: なぜ二分ヒープを直接使用しないのですか？
二分ヒープはシンプルな配列レイアウトと安定した計算量境界を持ちます。ペアリングヒープは meld や頻繁な decrease-key において定数倍がより小さくなる可能性があります。操作の比率、メモリ局所性、および証明の要件に応じて選択します。
フォローアップ 2: decrease-key で兄弟の走査を回避するにはどうすればよいですか？
prevSibling ポインタや子セットのインデックスを追加します。ただし、link や cut のたびにより多くのポインタを維持する必要があります。その空間およびメンテナンスコストを走査コストと比較検討します。
フォローアップ 3: 任意のハンドルを削除するにはどうすればよいですか？
そのキーを負の無限大に下げ、decrease-key を呼び出した後、delete-min を呼び出します。コンパレータと番兵（sentinel）が安全であることを確認し、ハンドルを正しく無効化します。
フォローアップ 4: フィボナッチヒープをどのような場合に選択しますか？
実装の複雑さよりも、理論的な decrease-key のならし計算量境界とアルゴリズムの厳密な証明が重要である場合に検討します。エンジニアリングの実装では、局所性、メモリ、および実際のワークロードの測定が依然として必要です。