Home Algoritmos y Estructuras de Datos (VJ1215)

Curso 2022/2023

Ejemplo de error en el ejercicio 4 del tema 2

Piensa qué es lo que está mal en la siguiente solución, y corrígelo.

void ColaDePrioridad::eliminarMinimo() {
   if (primero == nullptr)
      throw string("Intentando eliminar el minimo en una cola de prioridad vacia");

   // Eliminar el minimo:
   for (actual = primero; actual != nullptr; actual = actual->siguiente)
      if (actual->siguiente == minimo) {
	 actual->siguiente = minimo->siguiente;
	 break;
      }
   delete minimo;

   // Buscar el nuevo minimo:
   minimo = nullptr;
   for (Nodo * actual = primero; actual != nullptr; actual = actual->siguiente)
      if (minimo == nullptr || actual->prioridad < minimo->prioridad)
	 minimo = actual;
}
      

Solución

Falta actualizar primero si coincide con minimo:

void ColaDePrioridad::eliminarMinimo() {
   if (primero == nullptr)
      throw string("Intentando eliminar el minimo en una cola de prioridad vacia");

   // Eliminar el minimo:
   if (primero == minimo)
      primero = minimo->siguiente;
   else
      for (actual = primero; actual != nullptr; actual = actual->siguiente)
	 if (actual->siguiente == minimo) {
	    actual->siguiente = minimo->siguiente;
	    break;
	 }
   delete minimo;

   // Buscar el nuevo minimo:
   minimo = nullptr;
   for (Nodo * actual = primero; actual != nullptr; actual = actual->siguiente)
      if (minimo == nullptr || actual->prioridad < minimo->prioridad)
	 minimo = actual;
}