Algoritmos y Estructuras de Datos (VJ1215)

Recordando el ejercicio 3 del tema 5.1, el algoritmo de Huffman consta de dos etapas:

1. Inicialmente inserta n datos en una cola de prioridad.

2. A continuación hace n iteraciones, en cada una de las cuales realiza dos operaciones de eliminación del mínimo y una operación de inserción.

Con un montículo de Fibonacci, el coste en el peor caso de la etapa 1 sería O(n) y el coste en el peor caso de la etapa 2 sería O(n log n), porque el algoritmo realiza una secuencia de operaciones y el coste en el peor caso de la secuencia lo obtenemos teniendo en cuenta los costes amortizados de las operaciones. Por tanto, el coste temporal del algoritmo sería O(n + n log n) = O(n log n) en el peor caso.