Montón AF

En ciencias de la computación , el AF-heap es un tipo de cola de prioridad para datos enteros, una extensión del árbol de fusión que utiliza un heap atómico propuesto por ML Fredman y DE Willard . ^{[ 1 ]}

Utilizando un AF-heap, es posible realizar m operaciones de inserción o disminución de clave y n operaciones de eliminación de mínimo en claves enteras de máquina en tiempo O ( m + n log n / log log n ) . Esto permite que el algoritmo de Dijkstra se realice en el mismo límite de tiempo O ( m + n log n / log log n ) en grafos con n aristas y m vértices, y conduce a un algoritmo de tiempo lineal para árboles de expansión mínima , con la suposición para ambos problemas de que los pesos de las aristas del grafo de entrada son enteros de máquina en el modelo transdicotómico .

• Árbol de fusión