Curso 2024/2025
De las siguientes soluciones, tres son incorrectas, contienen errores de
programación básica, piensa cuáles son. La otra es ineficiente, piensa cuál
es y por qué. Supón que en todas ellas se hace uso de un
método insertar
implementado previamente, cuyo coste es O(1) cuando el elemento insertado
es el nuevo mínimo o el nuevo máximo.
void ColaDePrioridadDeDobleFin::unir(const ColaDePrioridadDeDobleFin & cola1, const ColaDePrioridadDeDobleFin & cola2) { vaciar(); Nodo * nodo1 = cola1.minimo, * nodo2 = cola2.minimo; while (nodo1 != nullptr && nodo2 != nullptr) if (nodo1->prioridad <= nodo2->prioridad) { insertar(nodo1->prioridad); nodo1 = nodo1->siguiente; } else { insertar(nodo2->prioridad); nodo2 = nodo2->siguiente; } }
Cuando se alcanza el final de una de las dos colas, pueden quedar elementos en la otra.
void ColaDePrioridadDeDobleFin::unir(const ColaDePrioridadDeDobleFin & cola1, const ColaDePrioridadDeDobleFin & cola2) { vaciar(); Nodo * nodo1 = cola1.minimo, * nodo2 = cola2.minimo; while (nodo1 != nullptr || nodo2 != nullptr) if (nodo1->prioridad <= nodo2->prioridad) { insertar(nodo1->prioridad); nodo1 = nodo1->siguiente; } else { insertar(nodo2->prioridad); nodo2 = nodo2->siguiente; } }
Si se alcanza el final de una de las colas antes que el final de la otra, eso va a fallar.
void ColaDePrioridadDeDobleFin::unir(const ColaDePrioridadDeDobleFin & cola1, const ColaDePrioridadDeDobleFin & cola2) { vaciar(); Nodo * nodo1 = cola1.minimo; while (nodo1 != nullptr) { insertar(nodo1->prioridad); nodo1 = nodo1->siguiente; } Nodo * nodo2 = cola2.minimo; while (nodo2 != nullptr) { insertar(nodo2->prioridad); nodo2 = nodo2->siguiente; } }
Cada llamada a insertar
en el primer bucle tiene coste O(1),
pera cada llamada a insertar
en el segundo bucle tiene
coste O(n). Por tanto, esta solución tiene coste
O(n2). Esto sucede, por ejemplo, si tenemos dos
colas de talla n y todos los elementos de la segunda cola
deben situarse justo antes del último elemento de la primera cola: [10,
20, 30, 40, 50, 60, 70, 80, 90, 100] y [90, 91, 92, 93, 94, 95, 96, 97,
98, 99].
void ColaDePrioridadDeDobleFin::unir(const ColaDePrioridadDeDobleFin & cola1, const ColaDePrioridadDeDobleFin & cola2) { vaciar(); return unir(cola1.minimo, cola2.minimo); } void ColaDePrioridadDeDobleFin::unir(Nodo * nodo1, Nodo * nodo2) { if (nodo1 != nullptr || nodo2 != nullptr) if (nodo2 == nullptr) { insertar(nodo1->prioridad); return unir(nodo1->siguiente, nodo2); } else if (nodo1 == nullptr) { insertar(nodo2->prioridad); return unir(nodo1, nodo2->siguiente); } else if (nodo1->prioridad <= nodo2->prioridad) { insertar(nodo1->prioridad); return unir(nodo1->siguiente, nodo2); } else { insertar(nodo2->prioridad); return unir(nodo1, nodo2->siguiente); } }
Sobra return
delante de cada llamada a un método que no
devuelve nada porque es void
.