Algoritmos y Estructuras de Datos - VJ1215

Solución del ejercicio 6.c del tema 2

Las siguientes 3 soluciones tiene coste temporal O(n) siendo n la talla de la cola de prioridad. Cada solución incluye los constructores que se encargan de hacer las inicializaciones necesarias.

Fíjate cómo se tratan los casos en que la cola de prioridad está vacía, el nuevo dato pasa a ser el mínimo o el nuevo dato pasa a ser el máximo. Tu solución puede ser diferente, pero debe funcionar correctamente también en cada uno de esos casos.

Solución 1

ColaDePrioridadDeDobleFin::Nodo::Nodo(int laPrioridad, Nodo * elAnterior, Nodo * elSiguiente)
  : prioridad{laPrioridad}, anterior{elAnterior}, siguiente{elSiguiente} {
}

ColaDePrioridadDeDobleFin::ColaDePrioridadDeDobleFin() 
  : minimo{nullptr}, maximo{nullptr} , laTalla{0} {
}

void ColaDePrioridadDeDobleFin::insertar(int prioridad) {

   laTalla++;

   if (minimo == nullptr) {
      minimo = new Nodo(prioridad, nullptr, nullptr);
      maximo = minimo;
   } else if (prioridad <= minimo->prioridad) {
      minimo = new Nodo(prioridad, nullptr, minimo);
      minimo->siguiente->anterior = minimo;
   } else if (prioridad >= maximo->prioridad) {
      maximo = new Nodo(prioridad, maximo, nullptr);
      maximo->anterior->siguiente = maximo;
   } else {
      for (Nodo * actual = minimo; actual != nullptr; actual = actual->siguiente) {
	 if (actual->prioridad >= prioridad) {
	    Nodo * nuevo = new Nodo(prioridad, actual->anterior, actual);
	    actual->anterior->siguiente = nuevo;
	    actual->anterior = nuevo;
	    return;
	 }
      }
   }
}

Solución 2

ColaDePrioridadDeDobleFin::Nodo::Nodo(int laPrioridad)
   : prioridad{laPrioridad}, anterior{nullptr}, siguiente{nullptr} {
}

ColaDePrioridadDeDobleFin::ColaDePrioridadDeDobleFin() 
   : minimo{nullptr}, maximo{nullptr} , laTalla{0} {
}

void ColaDePrioridadDeDobleFin::insertar(int prioridad) {

   laTalla++;
  
   Nodo * nuevo = new Nodo(prioridad);

   if (minimo == nullptr) {
      minimo = maximo = nuevo;
   } else if (prioridad <= minimo->prioridad) {
      nuevo->siguiente = minimo;
      minimo->anterior = nuevo;
      minimo           = nuevo;
   } else if (prioridad >= maximo->prioridad) {
      maximo->siguiente = nuevo;
      nuevo->anterior   = maximo;
      maximo            = nuevo;
   } else {
      Nodo * n = minimo;
      while (n->prioridad < prioridad) {
	 n = n->siguiente;
      }
      nuevo->anterior        = n->anterior;
      nuevo->siguiente       = n;
      n->anterior->siguiente = nuevo;
      n->anterior            = nuevo;
   }
}

Observa que, en esta solución, el bucle while siempre termina porque, tras las comprobaciones previas, al llegar a ese bucle seguro que el valor de prioridad no supera la del último nodo.

Solución 3 (recursiva)

ColaDePrioridadDeDobleFin::Nodo::Nodo(int laPrioridad, Nodo * elAnterior, Nodo * elSiguiente)
   : prioridad{laPrioridad}, anterior{elAnterior}, siguiente{elSiguiente} {
}

ColaDePrioridadDeDobleFin::ColaDePrioridadDeDobleFin() 
   : minimo{nullptr}, maximo{nullptr}, laTalla{0} {
}

void ColaDePrioridadDeDobleFin::insertar(int prioridad) {
   laTalla++;
   if (minimo == nullptr) {
      minimo = new Nodo(prioridad, nullptr, nullptr);
      maximo = minimo;
   } else if (prioridad <= minimo->prioridad) {
      minimo = new Nodo(prioridad, nullptr, minimo);
      minimo->siguiente->anterior = minimo;
   } else if (prioridad >= maximo->prioridad) {
      maximo = new Nodo(prioridad, maximo, nullptr);
      maximo->anterior->siguiente = maximo;
   } else
      insertar(prioridad, minimo);
}

void ColaDePrioridadDeDobleFin::insertar(int prioridad, Nodo * inicio) {
   // Sabemos que inicio != nullptr tras las comprobaciones anteriores
   if (inicio->prioridad >= prioridad) { // > o >=, en caso de empate podemos ponerlo delante o detras
      Nodo * nuevo = new Nodo(prioridad, inicio->anterior, inicio);
      inicio->anterior->siguiente = nuevo;
      inicio->anterior = nuevo;
   } else
      insertar(prioridad, inicio->siguiente);
}