Algoritmos y Estructuras de Datos - VJ1215

Solución del ejercicio 3.d del tema 2

Las siguientes soluciones tiene coste temporal O(n) siendo n la talla de la cola de prioridad.

Verifica que tu solución funciona correctamente en los siguientes casos:

si la cola de prioridad estaba vacía;
si había un solo dato;
si se elimina el mínimo; o
si se elimina el máximo.

Solución 1

void ColaDePrioridadDeDobleFin::eliminar(int prioridad) {
   for (Nodo * actual = minimo; actual != nullptr && actual->prioridad <= prioridad; actual = actual->siguiente) {
      if (actual->prioridad == prioridad) {
	 if (minimo == maximo) {
	    minimo = maximo = nullptr;
	 } else if (actual == minimo) {
	    minimo = minimo->siguiente;
	    minimo->anterior = nullptr;
	 } else if (actual == maximo) {
	    maximo = maximo->anterior;
	    maximo->siguiente = nullptr;
	 } else {
	    actual->anterior->siguiente = actual->siguiente;
	    actual->siguiente->anterior = actual->anterior;
	 }
	 delete actual;
	 laTalla--;
	 return;
      }
   }
   throw string("Intentando eliminar un elemento que no esta");
}

Observa bien las asignaciones en que hemos de poner nullptr donde hasta ahora teniamos la dirección del nodo eliminado: eso no sucede automáticamente al eliminarlo.

Los estudiantes preguntan

Pregunta 1 ¿Sería mejor comprobar si es el mínimo o el máximo antes del bucle, en vez de hacerlo en cada iteración?

Respuesta 1 No se hace en cada iteración, está dentro del bucle pero solo se hace una vez, cuando se encuentra el dato a eliminar.

Pregunta 2 En el caso minimo == maximo, ¿no faltaría comprobar si hay un solo elemento o hay varios elementos iguales?

Respuesta 2 Si el contenido de la cola de prioridad son n elementos iguales, hay n nodos; si n > 1, minimo es la dirección de un nodo, maximo es la dirección de otro nodo, y no se cumple minimo == maximo. Si, en ese bucle, minimo == maximo, es porque hay un solo nodo.

Solución 2 (recursiva)

void ColaDePrioridadDeDobleFin::eliminar(int prioridad) {
   eliminar(prioridad, minimo);
}

void ColaDePrioridadDeDobleFin::eliminar(int prioridad, Nodo * inicio) {
   if (inicio == nullptr || inicio->prioridad > prioridad)
      throw string("Intentando eliminar un elemento que no esta");

   if (inicio->prioridad == prioridad) {
      if (inicio->siguiente != nullptr)
	 inicio->siguiente->anterior = inicio->anterior;
      else
	 maximo = inicio->anterior;
      if (inicio->anterior != nullptr)
	 inicio->anterior->siguiente = inicio->siguiente;
      else
	 minimo = inicio->siguiente;
      delete inicio;
      laTalla--;
   } else
      eliminar(prioridad, inicio->siguiente);
}