C# cola de prioridad

Question

Busco una cola de prioridad con una interfaz de la siguiente manera:

class PriorityQueue<T> 
{ 
    public void Enqueue(T item, int priority) 
    { 
    } 

    public T Dequeue() 
    { 
    } 
} 

Todas las implementaciones que he visto asuma que es un itemIComparable pero no me gusta este enfoque; Quiero especificar la prioridad cuando la coloque en la cola.

Si no existe una implementación ya hecha, ¿cuál es la mejor manera de hacerlo yo mismo? ¿Qué estructura de datos subyacente debería usar? Algún tipo de árbol de auto-equilibrio, o qué? Una estructura estándar de C# .net sería agradable.

Answer 1

Si usted tiene una aplicación de cola de prioridad existente, basado en IComparable, puede utilizar fácilmente que para construir la estructura que necesita:

public class CustomPriorityQueue<T> // where T need NOT be IComparable 
{ 
    private class PriorityQueueItem : IComparable<PriorityQueueItem> 
    { 
    private readonly T _item; 
    private readonly int _priority: 

    // obvious constructor, CompareTo implementation and Item accessor 
    } 

    // the existing PQ implementation where the item *does* need to be IComparable 
    private readonly PriorityQueue<PriorityQueueItem> _inner = new PriorityQueue<PriorityQueueItem>(); 

    public void Enqueue(T item, int priority) 
    { 
    _inner.Enqueue(new PriorityQueueItem(item, priority)); 
    } 

    public T Dequeue() 
    { 
    return _inner.Dequeue().Item; 
    } 
} 

Answer 2

Parece que podría hacer las suyas con una serie de Colas, una para cada prioridad. Diccionario y simplemente agréguelo al apropiado.

Answer 3

Usted puede agregar controles de seguridad y lo que no, pero aquí hay una aplicación muy sencilla usando SortedList:

class PriorityQueue<T> { 
    SortedList<Pair<int>, T> _list; 
    int count; 

    public PriorityQueue() { 
     _list = new SortedList<Pair<int>, T>(new PairComparer<int>()); 
    } 

    public void Enqueue(T item, int priority) { 
     _list.Add(new Pair<int>(priority, count), item); 
     count++; 
    } 

    public T Dequeue() { 
     T item = _list[_list.Keys[0]]; 
     _list.RemoveAt(0); 
     return item; 
    } 
} 

Estoy asumiendo que los valores más pequeños de priority corresponden a los elementos de mayor prioridad (esto es fácil de modificar)

Si hay varios hilos que accederán a la cola, deberá agregar también un mecanismo de bloqueo. Esto es fácil, pero avíseme si necesita orientación aquí.

SortedList se implementa internamente como un árbol binario.

La implementación anterior necesita las siguientes clases de ayuda. Esta dirección Lasse V. Comentario de Karlsen que los elementos con la misma prioridad no se pueden agregar usando la implementación ingenua usando un SortedList.

class Pair<T> { 
    public T First { get; private set; } 
    public T Second { get; private set; } 

    public Pair(T first, T second) { 
     First = first; 
     Second = second; 
    } 

    public override int GetHashCode() { 
     return First.GetHashCode()^Second.GetHashCode(); 
    } 

    public override bool Equals(object other) { 
     Pair<T> pair = other as Pair<T>; 
     if (pair == null) { 
      return false; 
     } 
     return (this.First.Equals(pair.First) && this.Second.Equals(pair.Second)); 
    } 
} 

class PairComparer<T> : IComparer<Pair<T>> where T : IComparable { 
    public int Compare(Pair<T> x, Pair<T> y) { 
     if (x.First.CompareTo(y.First) < 0) { 
      return -1; 
     } 
     else if (x.First.CompareTo(y.First) > 0) { 
      return 1; 
     } 
     else { 
      return x.Second.CompareTo(y.Second); 
     } 
    } 
} 

Answer 4

Se podría escribir una envoltura alrededor de una de las implementaciones existentes que modifica la interfaz a su preferencia:

using System; 

class PriorityQueueThatYouDontLike<T> where T: IComparable<T> 
{ 
    public void Enqueue(T item) { throw new NotImplementedException(); } 
    public T Dequeue() { throw new NotImplementedException(); } 
} 

class PriorityQueue<T> 
{ 
    class ItemWithPriority : IComparable<ItemWithPriority> 
    { 
     public ItemWithPriority(T t, int priority) 
     { 
      Item = t; 
      Priority = priority; 
     } 

     public T Item {get; private set;} 
     public int Priority {get; private set;} 

     public int CompareTo(ItemWithPriority other) 
     { 
      return Priority.CompareTo(other.Priority); 
     } 
    } 

    PriorityQueueThatYouDontLike<ItemWithPriority> q = new PriorityQueueThatYouDontLike<ItemWithPriority>(); 

    public void Enqueue(T item, int priority) 
    { 
     q.Enqueue(new ItemWithPriority(item, priority)); 
    } 

    public T Dequeue() 
    { 
     return q.Dequeue().Item; 
    } 
} 

Esto es lo mismo que la sugerencia de itowlson. Me tomó más tiempo escribir el mío porque completé más métodos. : -s

Answer 5

Aquí hay una implementación liviana muy simple que tiene un rendimiento O (log (n)) tanto para push como para pop. Utiliza un heap data structure incorporado en la parte superior de una lista <T>.

/// <summary>Implements a priority queue of T, where T has an ordering.</summary> 
/// Elements may be added to the queue in any order, but when we pull 
/// elements out of the queue, they will be returned in 'ascending' order. 
/// Adding new elements into the queue may be done at any time, so this is 
/// useful to implement a dynamically growing and shrinking queue. Both adding 
/// an element and removing the first element are log(N) operations. 
/// 
/// The queue is implemented using a priority-heap data structure. For more 
/// details on this elegant and simple data structure see "Programming Pearls" 
/// in our library. The tree is implemented atop a list, where 2N and 2N+1 are 
/// the child nodes of node N. The tree is balanced and left-aligned so there 
/// are no 'holes' in this list. 
/// <typeparam name="T">Type T, should implement IComparable[T];</typeparam> 
public class PriorityQueue<T> where T : IComparable<T> { 
    /// <summary>Clear all the elements from the priority queue</summary> 
    public void Clear() { 
     mA.Clear(); 
    } 

    /// <summary>Add an element to the priority queue - O(log(n)) time operation.</summary> 
    /// <param name="item">The item to be added to the queue</param> 
    public void Add (T item) { 
     // We add the item to the end of the list (at the bottom of the 
     // tree). Then, the heap-property could be violated between this element 
     // and it's parent. If this is the case, we swap this element with the 
     // parent (a safe operation to do since the element is known to be less 
     // than it's parent). Now the element move one level up the tree. We repeat 
     // this test with the element and it's new parent. The element, if lesser 
     // than everybody else in the tree will eventually bubble all the way up 
     // to the root of the tree (or the head of the list). It is easy to see 
     // this will take log(N) time, since we are working with a balanced binary 
     // tree. 
     int n = mA.Count; mA.Add (item); 
     while (n != 0) { 
     int p = n/2; // This is the 'parent' of this item 
     if (mA[n].CompareTo (mA[p]) >= 0) break; // Item >= parent 
     T tmp = mA[n]; mA[n] = mA[p]; mA[p] = tmp; // Swap item and parent 
     n = p;   // And continue 
     } 
    } 

    /// <summary>Returns the number of elements in the queue.</summary> 
    public int Count { 
     get { return mA.Count; } 
    } 

    /// <summary>Returns true if the queue is empty.</summary> 
    /// Trying to call Peek() or Next() on an empty queue will throw an exception. 
    /// Check using Empty first before calling these methods. 
    public bool Empty { 
     get { return mA.Count == 0; } 
    } 

    /// <summary>Allows you to look at the first element waiting in the queue, without removing it.</summary> 
    /// This element will be the one that will be returned if you subsequently call Next(). 
    public T Peek() { 
     return mA[0]; 
    } 

    /// <summary>Removes and returns the first element from the queue (least element)</summary> 
    /// <returns>The first element in the queue, in ascending order.</returns> 
    public T Next() { 
     // The element to return is of course the first element in the array, 
     // or the root of the tree. However, this will leave a 'hole' there. We 
     // fill up this hole with the last element from the array. This will 
     // break the heap property. So we bubble the element downwards by swapping 
     // it with it's lower child until it reaches it's correct level. The lower 
     // child (one of the orignal elements with index 1 or 2) will now be at the 
     // head of the queue (root of the tree). 
     T val = mA[0]; 
     int nMax = mA.Count - 1; 
     mA[0] = mA[nMax]; mA.RemoveAt (nMax); // Move the last element to the top 

     int p = 0; 
     while (true) { 
     // c is the child we want to swap with. If there 
     // is no child at all, then the heap is balanced 
     int c = p * 2; if (c >= nMax) break; 

     // If the second child is smaller than the first, that's the one 
     // we want to swap with this parent. 
     if (c + 1 < nMax && mA[c + 1].CompareTo (mA[c]) < 0) c++; 
     // If the parent is already smaller than this smaller child, then 
     // we are done 
     if (mA[p].CompareTo (mA[c]) <= 0) break; 

     // Othewise, swap parent and child, and follow down the parent 
     T tmp = mA[p]; mA[p] = mA[c]; mA[c] = tmp; 
     p = c; 
     } 
     return val; 
    } 

    /// <summary>The List we use for implementation.</summary> 
    List<T> mA = new List<T>(); 
} 

Answer 6

¿Qué sería tan terrible acerca de algo como esto?

class PriorityQueue<TItem, TPriority> where TPriority : IComparable 
{ 
    private SortedList<TPriority, Queue<TItem>> pq = new SortedList<TPriority, Queue<TItem>>(); 
    public int Count { get; private set; } 

    public void Enqueue(TItem item, TPriority priority) 
    { 
     ++Count; 
     if (!pq.ContainsKey(priority)) pq[priority] = new Queue<TItem>(); 
     pq[priority].Enqueue(item); 
    } 

    public TItem Dequeue() 
    { 
     --Count; 
     var queue = pq.ElementAt(0).Value; 
     if (queue.Count == 1) pq.RemoveAt(0); 
     return queue.Dequeue(); 
    } 
} 

class PriorityQueue<TItem> : PriorityQueue<TItem, int> { } 

Answer 7

que se dan cuenta de que su pregunta se refiere específicamente para una aplicación no basada en IComparable, pero quiero señalar un reciente artículo de Visual Studio Magazine.

http://visualstudiomagazine.com/articles/2012/11/01/priority-queues-with-c.aspx

Este artículo con @ de itowlson puede dar una respuesta completa.

Answer 8

Esa es la interfaz exacta utilizada por mi highly optimized C# priority-queue.

Fue desarrollado específicamente para aplicaciones de pathfinding (A *, etc.), pero debería funcionar perfectamente para cualquier otra aplicación también.

El único problema posible es que, para exprimir el máximo rendimiento absoluto, la implementación requiere que los valores en cola se extiendan a PriorityQueueNode.

public class User : PriorityQueueNode 
{ 
    public string Name { get; private set; } 
    public User(string name) 
    { 
     Name = name; 
    } 
} 

... 

HeapPriorityQueue<User> priorityQueue = new HeapPriorityQueue<User>(MAX_USERS_IN_QUEUE); 
priorityQueue.Enqueue(new User("Jason"), 1); 
priorityQueue.Enqueue(new User("Joseph"), 10); 

//Because it's a min-priority queue, the following line will return "Jason" 
User user = priorityQueue.Dequeue(); 

Answer 9

un poco tarde, pero voy a añadir aquí como referencia

https://github.com/ERufian/Algs4-CSharp

clave-valor de par colas de prioridad se implementan en Algs4/IndexMaxPQ.cs, Algs4/IndexMinPQ.cs y Algs4/IndexPQDictionary.cs

Notas:

1. Si las prioridades no se IComparable' s, se puede especificar un IComparer en el constructor
2. En lugar de enqueuear el objeto y su prioridad, lo que se pone en cola es un índice y su prioridad (y, para la pregunta original, se necesitaría una Lista o T [] separada para convertir ese índice al resultado esperado)