C# File D'Attente De Priorité

Vous pouvez ajouter des contrôles de sécurité et de ce pas, mais en voici une très simple de mise en œuvre à l'aide de 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;
    }
}

Je suis en supposant que les petites valeurs de priority correspondent à des éléments prioritaires (c'est facile à modifier).

Si plusieurs threads accèdent à la file d'attente, vous aurez besoin d'ajouter un mécanisme de verrouillage de trop. C'est facile, mais laissez-moi savoir si vous avez besoin de conseils ici.

SortedList est mis en œuvre, en interne comme un arbre binaire.

Ci-dessus la mise en œuvre besoins suivants des classes d'assistance. Cette adresse Lasse V. Karlsen dans son commentaire que les articles avec le même niveau de priorité ne peut pas être ajoutée à l'aide de la naïveté de la mise en œuvre à l'aide d'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);
}
}
}

Voici une très simple léger de mise en œuvre est O(log(n)) une performance à la fois push et pop. Il utilise un tas de structure de données construit sur une Liste<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> ();
}

Ce serait si terrible au sujet de quelque chose comme cela?

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> { }

Un peu en retard mais je vais ajouter ici pour référence

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

Clé-valeur de la paire de files d'attente de priorité sont mis en œuvre dans Algs4/IndexMaxPQ.cs, Algs4/IndexMinPQ.cs et Algs4/IndexPQDictionary.cs

Notes:

1. Si les Priorités ne sont pas IComparable, un IComparer peut être spécifié dans le constructeur
2. Au lieu de enqueueing l'objet et de sa priorité, ce qui est mis en file d'attente est un indice et sa priorité (et, pour la question d'origine, une Liste séparée ou T[] serait nécessaire pour convertir l'indice du résultat attendu)