Revisión de código

Revisa este código de un agente

Para cambiar la prioridad de una tarea en un heap, un agente escribió:

Texto

1  para i desde 0 hasta longitud(h) − 1:2      si h[i].tarea = t:3          h[i].prioridad ← nueva4  construir(h)          # reconstruye el heap entero

Para cambiar la prioridad de una tarea t en un heap h, un agente recorre todo el array h hasta encontrar t, le asigna la prioridad nueva y llama a construir(h) para reconstruir el heap. ¿Qué cuesta y qué alternativa hay?O(n) para buscar y otro O(n) al reconstruir; con índice de posiciones y subir o bajar, O(log n)O(n log n): el bucle recorre n elementos y construir cuesta n log nO(log n), porque es un heap: el bucle solo localiza la tarea y el resto es baratoO(n) por el bucle, y la reconstrucción sobra: basta cambiar la prioridad y seguir