algorithm - Cola de prioridad con prioridades de elementos dinámicos

heap priority-queue

Question

Necesito implementar una cola de prioridad donde la prioridad de un elemento en la cola pueda cambiar y la cola se ajuste 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 puede decirme el nombre de este tipo de cola de prioridad para saber qué buscar o, mejor aún, señalarme una implementación?

Answer 1

Estoy buscando exactamente lo mismo!

Y aquí está algo de mi idea:

1. Dado que la prioridad de un elemento sigue cambiando, no tiene sentido ordenar la cola antes de recuperar un elemento.
2. Entonces, debemos olvidarnos de usar una cola de prioridad. Y "parcialmente" ordena el contenedor mientras recupera un artículo.

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

partition, stable_partition y nth_element son algoritmos de ordenación de tiempo lineal, que deberían ser nuestras primeras elecciones.

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

Answer 2

Las colas de prioridad como esta se implementan normalmente utilizando una estructura de datos de montón binario como lo sugirió otra persona, que generalmente se representa mediante 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 de la cola el siguiente elemento, puede desactivar temporalmente la reordenación dinámica, 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 se haga estallar el elemento. Lo importante de los montones es que solo le cuesta a O (n) poner una matriz en el orden de almacenamiento, pero O (n log n) ordenarla.

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

Aquí está mi implementación de una implementación de cola de prioridad parametrizada en el lenguaje de programación Curl .

Answer 3

Un montón binario estándar admite 5 operaciones (el siguiente ejemplo asume un montón máximo):

* 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 puede ver, en un montón máximo, puede aumentar una clave arbitraria. En un montón min puede disminuir una clave arbitraria. Lamentablemente, no se pueden cambiar las teclas en ambos sentidos, pero ¿esto funcionará? Si necesita cambiar las claves de ambas maneras, entonces debería pensar en usar aa min-max-heap .

Answer 4

Yo sugeriría primero probar el enfoque frontal, para actualizar una prioridad:

• eliminar el elemento de la cola
• reinsértalo 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 suponer que sabe nada 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 5

Google tiene varias respuestas para usted, incluida una implementación de una en Java .

Sin embargo, esto suena como algo que sería un problema con la tarea, por lo que si lo fuera, sugeriría que primero intente trabajar con las ideas, y luego hacer referencia a la implementación de otra persona si se queda atascado en algún lugar y necesita un indicador en la dirección correcta . De esa manera, es menos probable que esté "sesgado" hacia el método de codificación preciso utilizado por el otro programador y es más probable que comprenda por qué se incluye cada fragmento de código y cómo funciona. A veces puede ser demasiado tentador hacer el parafraseo equivalente de "copiar y pegar".