Куча АФ

В информатике AF -куча — это тип приоритетной очереди для целочисленных данных, расширение слитого дерева с использованием атомной кучи, предложенное М.Л. Фредманом и Д.Э. Уиллардом . ^{[ 1 ]}

Используя AF-кучу, можно выполнить $m$ операций вставки или уменьшения ключа и $n$ операций удаления-мин на машинно-целочисленных ключах за время $O (m + n log n / log log n)$ . Это позволяет алгоритму Дейкстры выполняться за одно и то же $время O (m + n log n /log log n)$ на графах с $n$ ребрами и $m$ вершинами и приводит к алгоритму с линейным временем для минимальных остовных деревьев с предположением как для проблемы, связанные с тем, что веса ребер входного графа являются машинными целыми числами в трансдихотомической модели .

См. также

Дерево слияния

Ссылки

^ М.Л. Фредман и Д.Э. Уиллард. Трансдихотомические алгоритмы для минимальных остовных деревьев и кратчайших путей. Журнал компьютерных и системных наук 48, 533–551 (1994).

Эта алгоритмам или структурам данных, статья, посвященная является незавершенной . Вы можете помочь Википедии, расширив ее .

Эта комбинаторике статья, посвященная , незавершена . Вы можете помочь Википедии, расширив ее .

[Willard-1] М.Л. Фредман и Д.Э. Уиллард. Трансдихотомические алгоритмы для минимальных остовных деревьев и кратчайших путей. Журнал компьютерных и системных наук 48, 533–551 (1994).

[ 1 ]