Algoritmos y Estructuras de Datos - VJ1215

Solución del ejercicio 6.h del tema 2

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.

Solución 1

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;
   }
   
}

Solución 2

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;
      }
   }

}

Solución 3

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;
      }
   }

}

Solución 4

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;
   }

}

Solución 5

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;
   }

}

Solución 6 (recursiva)

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);
      }
   }
   
}

Solución 7 (recursiva)

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);
      }
   }

}