Algoritmos y Estructuras de Datos - VJ1215

Solución del ejercicio 3 del tema 2

Para conseguir que las operaciones tengan los costes que se piden, utilizaremos una lista simplemente enlazada en la que cada nuevo dato se inserta en cabeza de la lista, y añadiremos un atributo para acceder directamente al nodo con el dato mínimo. De ese modo, podemos consultar el mínimo en tiempo O(1), y también podemos realizar la operación de inserción en tiempo O(1) manteniendo ese atributo actualizado. La operación de eliminación del mínimo tendrá que buscar el nuevo mínimo y tendrá coste temporal O(n), siendo n la talla de la cola de prioridad.

Declaración de atributos y métodos

class ColaDePrioridad {

   struct Nodo {
      int prioridad;
      Nodo * siguiente;
      Nodo(int, Nodo *);
   };

   Nodo * primero, * minimo;

 public:

   ColaDePrioridad();
  
   void insertar(int);

   int consultarMinimo() const;

   void eliminarMinimo();

};

`insertar` y constructores de los que depende

ColaDePrioridad::Nodo::Nodo(int laPrioridad, Nodo * elSiguiente)
   : prioridad{laPrioridad}, siguiente{elSiguiente} {
}

ColaDePrioridad::ColaDePrioridad() : primero{nullptr}, minimo{nullptr} {
}
  
void ColaDePrioridad::insertar(int prioridad) {
   primero = new Nodo(prioridad, primero);

   if (minimo == nullptr || primero->prioridad < minimo->prioridad)
      minimo = primero;
}

`consultarMinimo`

int ColaDePrioridad::consultarMinimo() const {
   if (minimo == nullptr)
      throw string("Intentando consultar el minimo en una cola de prioridad vacia");

   return minimo->prioridad;
}

`eliminarMinimo` (versión 1)

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

   // Eliminar el minimo:
   if (minimo == primero)
      primero = primero->siguiente;
   else {
      Nodo * anterior;
      for (anterior = primero; anterior->siguiente != minimo; anterior = anterior->siguiente) {
      }
      anterior->siguiente = minimo->siguiente;
   }
   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;
}

`eliminarMinimo` (versión 2)

En la siguiente versión se utiliza un solo bucle para realizar lo que en la versión anterior se hace con dos bucles. Ambas versiones tienen coste temporal O(n).

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

   Nodo * nuevoMinimo = nullptr, * anterior = nullptr;
   for (Nodo * actual = primero; actual != nullptr; actual = actual->siguiente) {
      if (actual == minimo) {
	 if (anterior == nullptr) {
	    primero = minimo->siguiente;
	 } else {
	    anterior->siguiente = minimo->siguiente;
	 }
      } else {
	 if (nuevoMinimo == nullptr || actual->prioridad < nuevoMinimo->prioridad) {
	    nuevoMinimo = actual;
	 }
      }
      anterior = actual;
   }
   delete minimo;
   minimo = nuevoMinimo;
}