Seguí las instrucciones dadas en this question (la respuesta de Jason) para escribir mi PriorityQueue<T> usando SortedList. Entiendo que el campo count dentro de esta clase se usa para garantizar prioridades únicas y para preservar el orden de puesta en secuencia entre la misma prioridad.Cambiar la prioridad en una cola de prioridad personalizada
Sin embargo, cuando count alcanza su valor máximo y yo suma 1, este último comenzará de nuevo desde 0, por lo que la prioridad de los elementos posteriores sería mayor que la prioridad de los elementos anteriores. El uso de este enfoque que pudiera necesitar una manera de "seguridad" restablecer el contador count ... De hecho, supongo que tienen el siguiente estado de la cola (en el formato de prioridad | contar | elemento):
0 | 123 | A
0 | 345 | B
1 | 234 | C
2 | 200 | D
Ahora supongamos que ha llegado el límite del contador, por lo que tengo que restablecerlo a 0: como consecuencia, el siguiente elemento insertado tendrá contador 0: por ejemplo, si inserto un elemento con prioridad igual a 1, se insertará incorrectamente antes de 1 | 234 | D
0 | 123 | A
0 | 345 | B
1 | 000 | nuevo elemento
1 | 234 | C
2 | 200 | D
El problema de la prioridad puede ser resuelto mediante la implementación de un majano creé una clase Heap, entonces utilicé Heap<KeyValuePair<TPriority, TElement> y una costumbre PriorityComparer con el fin de ordenar los elementos por TPriority. Dada TPriority como int y TElement como string, la PriorityComparer es el siguiente:
public class MyComparer : IComparer<KeyValuePair<int, string>>
{
public int Compare(KeyValuePair<int, string> x, KeyValuePair<int, string> y)
{
return x.Key.CompareTo(y.Key);
}
}
...
int capacity = 10;
Heap<KeyValuePair<int, string>> queue;
queue = new Heap<KeyValuePair<int, string>>(capacity, new PriorityComparer());
...
ACTUALIZACIÓN De esta manera (con el PriorityComparer), he tenido éxito para implementar una cola de prioridad. Ahora me gustaría agregar soporte para modificar su comportamiento en el tiempo de ejecución, es decir, cambiar de FIFO a clasificación de prioridad y viceversa. Ya que mi aplicación de cola de prioridad tiene un campo IComparer, creo que es suficiente con añadir una propiedad Comparer a editar este campo, como los siguientes:
public IComparer
{
set
{
this._comparer = value;
}
}
Mientras tanto, yo pensé en tomar un enfoque diferente: en lugar de usar un montón binario para administrar las prioridades, podría ajustar diferentes colas (cada cola se refiere a una prioridad dada) de la siguiente manera.
public class PriorityQueue<T, int>
{
private Queue<T> _defaultQueue;
private bool _priority;
private SortedList<int, Queue<T>> _priorityQueues;
public PriorityQueue(int capacity)
{
this._defaultQueue = new Queue<T>(capacity);
this._priority = false;
this._priorityQueues = new SortedList<int, Queue<T>>(0);
}
public void PriorityEnable()
{
this._priority = true;
}
public void PriorityDisable()
{
this._priority = false;
}
public void Enqueue(T item)
{
if (this._priority)
{
// enqueue to one of the queues
// with associated priority
// ...
}
else this._defaultQueue.Enqueue(item);
}
public T Dequeue()
{
if (this._priority)
{
// dequeue from one of the queues
// with associated priority and
// return
// ...
}
return this._defaultQueue.Dequeue();
}
}
- Cómo gestionar la transición de modo FIFO a modo de prioridad cuando todavía hay elementos en la cola por defecto? Podría copiarlos en las colas de prioridad basadas en la prioridad del artículo ... ¿Otras soluciones mejores?
- Cómo administrar la transición de modo de prioridad a Modo FIFO? En este caso, tendría varias colas de prioridad, que pueden contener elementos, pero ya no tienen que administrarlas de acuerdo con la prioridad y ni siquiera saber el orden de llegada original ...
- ¿Cómo puedo gestionar la capacidad de los diferentes colas?
- ¿Qué hay de las prestaciones de las dos soluciones anteriores? ¿Qué usa más memoria?
¿Mi respuesta es útil para su problema? – JeremyK