Cola de prioridad con prioridades de elementos dinámicos

Question

Necesito implementar una cola de prioridad donde la prioridad de un elemento en la cola puede cambiar y la cola se ajusta para que los elementos siempre se eliminen en el orden correcto. Tengo algunas ideas de cómo podría implementar esto, pero estoy seguro de que esta es una estructura de datos bastante común, así que espero poder usar una implementación de alguien más inteligente que yo como base.

¿Alguien me puede decir el nombre de este tipo de cola de prioridad así que sé qué buscar o, mejor aún, señalarme una implementación?

Answer 1

Yo sugeriría tratando primero el acercamiento de frente en, para actualizar una prioridad:

• eliminar el elemento de la cola
• Reinsértela con la nueva prioridad

En C++, esto podría hacerse usando un std::multi_map, lo importante es que el objeto debe recordar dónde está almacenado en la estructura para poder eliminarse de manera eficiente. Para volver a insertarlo, es difícil ya que no puede presumir que sabe algo sobre las prioridades.

class Item; 

typedef std::multi_map<int, Item*> priority_queue; 

class Item 
{ 
public: 
    void add(priority_queue& queue); 
    void remove(); 

    int getPriority() const; 
    void setPriority(int priority); 

    std::string& accessData(); 
    const std::string& getData() const; 

private: 
    int mPriority; 
    std::string mData; 

    priority_queue* mQueue; 
    priority_queue::iterator mIterator; 
}; 

void Item::add(priority_queue& queue) 
{ 
    mQueue = &queue; 
    mIterator = queue.insert(std::make_pair(mPriority,this)); 
} 

void Item::remove() 
{ 
    mQueue.erase(mIterator); 
    mQueue = 0; 
    mIterator = priority_queue::iterator(); 
} 

void Item::setPriority(int priority) 
{ 
    mPriority = priority; 
    if (mQueue) 
    { 
    priority_queue& queue = *mQueue; 
    this->remove(); 
    this->add(queue); 
    } 
} 

Answer 2

Google has a number of answers para usted, incluyendo una implementación de one in Java.

Sin embargo, esto suena como un problema de tarea, así que si es así, sugiero tratar primero de resolver las ideas tú mismo, y luego hacer referencia a la implementación de otra persona si te quedas atascado y necesitas un puntero en la dirección correcta. De esta forma, es menos probable que esté "predispuesto" hacia el método de codificación preciso utilizado por el otro programador y más probable que comprenda por qué se incluye cada fragmento de código y cómo funciona. A veces puede ser un poco tentador hacer el equivalente parafraseante de "copiar y pegar".

Answer 3

Un montón binario estándar compatible con 5 operaciones (el ejemplo a continuación asumir un montón max):

* find-max: return the maximum node of the heap 
* delete-max: removing the root node of the heap 
* increase-key: updating a key within the heap 
* insert: adding a new key to the heap 
* merge: joining two heaps to form a valid new heap containing all the elements of both. 

Como se puede ver, en un montón max, puede aumentar una clave arbitraria. En un montón mínimo, puede disminuir una clave arbitraria. No se puede cambiar las llaves en ambos sentidos, lamentablemente, pero ¿lo hará? Si necesita cambiar las claves en ambos sentidos, entonces quizás quiera pensar en usar un min-max-heap.

Answer 4

¡Estoy buscando exactamente lo mismo!

Y aquí es un poco de mi idea:

1. Dado que una prioridad de un elemento cambia constantemente, no tiene sentido para ordenar la cola antes de recuperar un elemento.
2. Por lo tanto, debemos olvidarnos de utilizar una cola de prioridad. Y clasifique "parcialmente" el contenedor mientras recupera un artículo.

Y elija entre los siguientes algoritmos de ordenación STL: a. partición b. stable_partition c. nth_element d. partial_sort e. partial_sort_copy f. ordenar g.stable_sort

partition, stable_partition y nth_element son algoritmos de ordenamiento en tiempo lineal, que deberían ser nuestras primeras elecciones.

PERO, parece que no hay esos algoritmos en la biblioteca oficial de Java. Como resultado, le sugiero que use java.util.Collections.max/min para hacer lo que quiera.

Answer 5

Las colas de prioridad como esta se implementan típicamente utilizando una estructura de datos de montón binario como sugirió otra persona, que generalmente se representa utilizando una matriz pero también podría usar un árbol binario. En realidad, no es difícil aumentar o disminuir la prioridad de un elemento en el montón. Si sabe que está cambiando la prioridad de muchos elementos antes de que salga el siguiente elemento de la cola, puede desactivar temporalmente el reordenamiento dinámico, insertar todos los elementos al final del montón y luego reordenar todo el montón (a un costo de O (n)) justo antes de que el elemento deba saltar. Lo importante de montones es que solo cuesta O (n) colocar una matriz en orden de pila pero O (n log n) para ordenarla.

He utilizado este enfoque con éxito en un proyecto grande con prioridades dinámicas.

Aquí está mi implementación de un priority queue implementation in the Curl programming language parametrizado.