Curso 2024/2025
Las siguientes soluciones tienen coste temporal O(n)
siendo n la suma de las tallas iniciales de las tres colas de
prioridad. En ellas se hace uso de
un método insertar
implementado previamente, cuyo coste es O(1) cuando el elemento insertado
es 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; } } while (nodo1 != nullptr) { insertar(nodo1->prioridad); nodo1 = nodo1->siguiente; } while (nodo2 != nullptr) { insertar(nodo2->prioridad); nodo2 = nodo2->siguiente; } }
void ColaDePrioridadDeDobleFin::unir(const ColaDePrioridadDeDobleFin & cola1, const ColaDePrioridadDeDobleFin & cola2) { vaciar(); Nodo * nodo1 = cola1.minimo, * nodo2 = cola2.minimo; while (nodo1 != nullptr || nodo2 != nullptr) { if (nodo2 == nullptr) { insertar(nodo1->prioridad); nodo1 = nodo1->siguiente; } else if (nodo1 == nullptr) { insertar(nodo2->prioridad); nodo2 = nodo2->siguiente; } else if (nodo1->prioridad <= nodo2->prioridad) { insertar(nodo1->prioridad); nodo1 = nodo1->siguiente; } else { insertar(nodo2->prioridad); nodo2 = nodo2->siguiente; } } }
void ColaDePrioridadDeDobleFin::unir(const ColaDePrioridadDeDobleFin & cola1, const ColaDePrioridadDeDobleFin & cola2) { vaciar(); Nodo * nodo1 = cola1.minimo, * nodo2 = cola2.minimo; while (nodo1 != nullptr || nodo2 != nullptr) { if (nodo2 == nullptr || (nodo1 != nullptr && nodo1->prioridad <= nodo2->prioridad)) { insertar(nodo1->prioridad); nodo1 = nodo1->siguiente; } else { insertar(nodo2->prioridad); nodo2 = nodo2->siguiente; } } }
void ColaDePrioridadDeDobleFin::unir(const ColaDePrioridadDeDobleFin & cola1, const ColaDePrioridadDeDobleFin & cola2) { vaciar(); Nodo * nodo1 = cola1.minimo, * nodo2 = cola2.minimo; while (nodo1 != nullptr) { while (nodo2 != nullptr && nodo2->prioridad <= nodo1->prioridad) { insertar(nodo2->prioridad); nodo2 = nodo2->siguiente; } insertar(nodo1->prioridad); nodo1 = nodo1->siguiente; } while (nodo2 != nullptr) { insertar(nodo2->prioridad); nodo2 = nodo2->siguiente; } }
void ColaDePrioridadDeDobleFin::unir(const ColaDePrioridadDeDobleFin & cola1, const ColaDePrioridadDeDobleFin & cola2) { vaciar(); Nodo * nodo1 = cola1.minimo, * nodo2 = cola2.minimo; while (nodo1 != nullptr) { if (nodo2 != nullptr && nodo2->prioridad <= nodo1->prioridad) { insertar(nodo2->prioridad); nodo2 = nodo2->siguiente; } else { insertar(nodo1->prioridad); nodo1 = nodo1->siguiente; } } while (nodo2 != nullptr) { insertar(nodo2->prioridad); nodo2 = nodo2->siguiente; } }
void ColaDePrioridadDeDobleFin::unir(const ColaDePrioridadDeDobleFin & cola1, const ColaDePrioridadDeDobleFin & cola2) { vaciar(); unir(cola1.minimo, cola2.minimo); } void ColaDePrioridadDeDobleFin::unir(Nodo * nodo1, Nodo * nodo2) { if (nodo1 != nullptr || nodo2 != nullptr) { if (nodo2 == nullptr) { insertar(nodo1->prioridad); unir(nodo1->siguiente, nodo2); } else if (nodo1 == nullptr) { insertar(nodo2->prioridad); unir(nodo1, nodo2->siguiente); } else if (nodo1->prioridad <= nodo2->prioridad) { insertar(nodo1->prioridad); unir(nodo1->siguiente, nodo2); } else { insertar(nodo2->prioridad); unir(nodo1, nodo2->siguiente); } } }
void ColaDePrioridadDeDobleFin::unir(const ColaDePrioridadDeDobleFin & cola1, const ColaDePrioridadDeDobleFin & cola2) { vaciar(); unir(cola1.minimo, cola2.minimo); } void ColaDePrioridadDeDobleFin::unir(Nodo * nodo1, Nodo * nodo2) { if (nodo1 != nullptr || nodo2 != nullptr) { if (nodo2 == nullptr || (nodo1 != nullptr && nodo1->prioridad <= nodo2->prioridad)) { insertar(nodo1->prioridad); unir(nodo1->siguiente, nodo2); } else { insertar(nodo2->prioridad); unir(nodo1, nodo2->siguiente); } } }