sterta AF

W informatyce sterta AF jest rodzajem kolejki priorytetowej dla danych całkowitych, rozszerzeniem drzewa fuzyjnego wykorzystującego stertę atomową zaproponowaną przez ML Fredmana i DE Willarda .

Używając sterty AF, możliwe jest wykonanie m operacji wstawiania lub zmniejszania klawiszy oraz n operacji kasowania-min na maszynowych kluczach całkowitych w czasie O ( m + n log n / log log n ) . Pozwala to na wykonanie algorytmu Dijkstry w tym samym czasie O ( m + n log n / log log n ) związanym z grafami o n krawędziach i m wierzchołkach i prowadzi do algorytmu czasu liniowego dla minimalnych drzew rozpinających , z założeniem dla obu problem polegający na tym, że wagi krawędzi grafu wejściowego są liczbami całkowitymi maszyny w modelu transdychotomicznym .

Zobacz też

• Drzewo fuzji