Структуры типа AF-heap или атомарной кучи — это сугубо теоретический способ понизить асимптотическую сложность некоторых алгоритмов. В статье, где определяется AF-heap, несколько раз подчёркивается, что к реальному миру это никакого отношения не имеет, а работать эта куча будет при числе элементов 2^12^20. Кстати, алгоритм MST при этом всё равно не линейной сложности. Существование линейного нерандомизированного алгоритма для MST всё ещё под вопросом. Алгоритм Chazelle (2000 год) имеет среднюю линейную сложность, однако константа там по факту получается настолько большой, что в реальном мире всё равно гораздо выгоднее считать алгоритмами со сложность O(m ln n).

Зарегистрируйтесь на Хабре, чтобы оставить комментарий