私が考えている次の問題があります（よく知られている/標準だと思います）：
バイナリ最小ヒープ内の k 個の最小要素のリストが O(k) であることを確認します。
BFSの大きな最小ヒープをトラバースして、単純なキューの代わりに最小ヒープを維持することを考えていました。最初は、補助最小ヒープには大きな最小ヒープのルートが含まれています。各ステップで最小値を抽出し、そのすべての子 (最大 2) を追加します。アルゴリズムは、補助最小ヒープで k 抽出分後に停止します。補助最小ヒープのサイズは O(k) です (抽出された最小キーごとに、その子を挿入します。最大 2)。
問題は、extract-min の複雑さが O(log k) であるため、このアルゴリズムの複雑さが O(k log k) であることです。そして、O(k) で 1 つを見つけなければなりません。
使用できるアイデア/論文はありますか?
ありがとう！
「ヒープ選択アルゴリズム」をグーグル検索すると、「フレデリクソンのヒープ選択アルゴリズム」に出くわし、この論文（27ページ...）につながりました。
私は解決策を見つけたと思います。各ステップで、extract-min を実行する代わりに、increase-key を実行します。増分キー、挿入キー、および get-min の最悪の場合の時間が O(1) であるデータ構造を検索したところ、Brodal queueが見つかりました。
Brodal キューはフィボナッチ ヒープによって開発された概念に基づいているため、詳細については、フィボナッチ ヒープを参照してください。
したがって、各ステップでは、次の一連の操作があります。
min = get-min(補助ヒープ)
(v1, v2) を min の子とする
増加分 (補助ヒープ、ルート、v1)
挿入 (補助ヒープ、v2)
これら 4 つの操作のそれぞれは、O(1) の最悪の場合の複雑さを持ちます。