Curso 2022/2023
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.
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; } } } }
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) { // Parara porque minimo->prioridad < prioridad < maximo->prioridad n = n->siguiente; } nuevo->anterior = n->anterior; nuevo->siguiente = n; n->anterior->siguiente = nuevo; n->anterior = nuevo; } }
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); }