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