AF-heap とは

コンピュータ科学では、AFヒープは整数データの優先キューの一種であり、M. L. FredmanとD. E. Willardによって提案されたアトムヒープを使用する融合ツリーの拡張です。
AFヒープを使用すると、時刻O(m + n log n / log log n)の機械整数キーに対してm個の挿入または減少キー操作およびn delete-min操作を実行することが可能です。これにより、Dijkstraのアルゴリズムは、n個のエッジとm個の頂点を持つグラフ上の同じO(m + n log n / log log n)時間に実行され、最小スパニングツリーに対して線形時間アルゴリズムが導き出されます。入力グラフのエッジ重みが経粘膜モデルの機械整数であるという問題。