Algoritmos y Estructuras de Datos - VJ1215

Solución del ejercicio 4 del tema 2

Para conseguir que las operaciones tengan los costes que se piden, utilizaremos una lista simplemente enlazada en la que los datos no estarán en el orden en que son insertados sino ordenados de menor a mayor. De ese modo, podemos consultar el mínimo en tiempo O(1) accediendo al primer nodo, y también podemos realizar la operación de eliminación del mínimo en tiempo O(1). La operación de inserción tendrá que buscar la posición del nuevo dato para mantener ordenada la lista enlazada, y tendrá coste temporal O(n), siendo n la talla de la cola de prioridad.

Se proporcionan a continuación varias implementaciones válidas de la operación de inserción, todas ellas con el mismo coste temporal. En la primera versión recursiva se hace uso de un puntero pasado por referencia, asegúrate de que entiendes esa versión: en el tema 3 necesitarás tener eso claro.

Declaración de atributos y métodos

class ColaDePrioridad {

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

   Nodo * primero;

   // void insertar(float, Nodo * &); // Para la version 1
   // void insertar(float, Nodo *);   // Para la version 2

 public:

   ColaDePrioridad();
  
   void insertar(float);

   float consultarMinimo() const;

   void eliminarMinimo();

};

Constructores

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

ColaDePrioridad::ColaDePrioridad() : primero{nullptr} {
}

`insertar` (versión 1, recursiva)

El primero de los siguientes dos métodos es público y el segundo (el recursivo) es privado.

void ColaDePrioridad::insertar(float prioridad) {
   insertar(prioridad, primero);
}

void ColaDePrioridad::insertar(float prioridad, Nodo * & actual) {
   if (actual == nullptr || prioridad <= actual->prioridad)
      actual = new Nodo(prioridad, actual);
   else
      insertar(prioridad, actual->siguiente);
}

`insertar` (versión 2, recursiva)

El primero de los siguientes dos métodos es público y el segundo (el recursivo) es privado.

void ColaDePrioridad::insertar(float prioridad) {
   if (primero == nullptr || prioridad <= primero->prioridad)
      primero = new Nodo(prioridad, primero);
   else
      insertar(prioridad, primero);
}

void ColaDePrioridad::insertar(float prioridad, Nodo * actual) {
   if (actual->siguiente == nullptr || prioridad <= actual->siguiente->prioridad)
      actual->siguiente = new Nodo(prioridad, actual->siguiente);
   else
      insertar(prioridad, actual->siguiente);
}

`insertar` (versión 3, no recursiva)

void ColaDePrioridad::insertar(float prioridad) {
   if (primero == nullptr || prioridad <= primero->prioridad)
      primero = new Nodo(prioridad, primero);
   else {
      bool insertado = false;
      for (Nodo * actual = primero; ! insertado; actual = actual->siguiente)
	 if (actual->siguiente == nullptr || prioridad <= actual->siguiente->prioridad) {
	    actual->siguiente = new Nodo(prioridad, actual->siguiente);
	    insertado = true;
	 }
   }
}

`insertar` (versión 4, no recursiva)

void ColaDePrioridad::insertar(float prioridad) {
   if (primero == nullptr)
      primero = new Nodo(prioridad, nullptr);
   else if (prioridad <= primero->prioridad)
      primero = new Nodo(prioridad, primero);
   else {
      Nodo * actual = primero, * anterior;
      while (actual != nullptr && actual->prioridad < prioridad) {
	 anterior = actual;
	 actual = actual->siguiente;
      }
      anterior->siguiente = new Nodo(prioridad, actual);
   }
}

`consultarMinimo`

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

   return primero->prioridad;
}

`eliminarMinimo`

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

   Nodo * basura = primero;
   primero = primero->siguiente;
   delete basura;  
}