Priority Queue C#
J'imagine que tout le monde connait la class Queue du framework qui permet de faire des piles FIFO.
J'ai cherché une PriorityQueue dans le framework, mais je n'ai rien trouvé à ce sujet... Voici donc une classe générique TRES simple qui met cette fonctionnalité en place.
Les Enqueues et les Dequeues se font dans une complexité d'ordre O(log n) grâce à un arbre binaire, ce qui est assez rapide.
Une priority queue peut être utile quand certains éléments doivent absolument passer avant les autres. Par exemple, un prof qui veut imprimer un document avant des étudiants (si y'a 100 fichiers d'étudiants dans la liste d'attentes, le prof passera devant tout le monde :D).
Suite à la discussion dans les commentaires de cette source, j'ajoute que cet algorithme n'est peut-être pas le meilleur au niveau des performances (ceci dit on a quand même un O(log n) ce qui est très bien) mais il reste (comparé à d'autres solutions plus rapide) très simple à mettre en place. De plus, la place prise en mémoire est très faible (un tableau de n élément suffit).
Source / Exemple :
using System;
using System.Collections.Generic;
using System.Text;
/*************************************************************************************
*
namespace PriorityQueue
{
/// ---------------------------------------------------------------------------------
/// <summary>
/// PriorityQueue.
///
/// Note: Insertion are done in O(log n)
/// Note: Removal are done in O(log n)
/// </summary>
/// <typeparam name="T"> The type to store in the priority queue. This type needs to
/// implement the IComparable interface. </typeparam>
/// ---------------------------------------------------------------------------------
public class PriorityQueue<T> where T : IComparable<T>
{
private List<InnerItem> _innerList = new List<InnerItem>();
private int _innerIndex = -1;
/// ---------------------------------------------------------------------------------
/// <summary>
/// Enqueue a new item.
/// </summary>
/// <param name="item"> The item to enqueue. </param>
/// ---------------------------------------------------------------------------------
public void Enqueue(T item)
{
this._innerList.Add(new InnerItem(++this._innerIndex, item));
if (this._innerList.Count > 1) this.UpHeap(); // Reorder the tree if needed
}
/// ---------------------------------------------------------------------------------
/// <summary>
/// Dequeue.
/// </summary>
/// <returns> Return the first item in the queue. </returns>
/// ---------------------------------------------------------------------------------
public T Dequeue()
{
T first = this.Peek();
int count = this._innerList.Count - 1;
this._innerList[0] = this._innerList[count];
this._innerList.RemoveAt(count);
this._innerIndex--;
this.DownHeap();
return first;
}
/// ---------------------------------------------------------------------------------
/// <summary>
/// Get the first item in the queue.
/// </summary>
/// <returns> The first item. </returns>
/// ---------------------------------------------------------------------------------
public T Peek()
{
return this._innerList.Count > 0 ? this._innerList[0].Item : default(T);
}
/// ---------------------------------------------------------------------------------
/// <summary>
/// Reorder the tree (down->up).
/// </summary>
/// ---------------------------------------------------------------------------------
private void UpHeap()
{
int current = this._innerList.Count - 1;
int parent = (current - 1) / 2;
while (this._innerList[current].Item.CompareTo(this._innerList[parent].Item) < 0)
{
this.SwitchElements(current, parent);
current = parent;
parent = (current - 1) / 2;
}
}
/// ---------------------------------------------------------------------------------
/// <summary>
/// Reorder the tree (up->down).
/// </summary>
/// ---------------------------------------------------------------------------------
private void DownHeap()
{
int best = 0; int current = -1;
int left = 0; int right = 0;
while(best != current)
{
current = best;
left = 2 * best + 1;
right = left + 1;
if (this._innerList.Count > left)
{
int x = this._innerList[best].Item.CompareTo(this._innerList[left].Item);
if (x > 0 || (x == 0 && this._innerList[left].Index < this._innerList[best].Index)) best = left;
}
if (this._innerList.Count > right)
{
int x = this._innerList[best].Item.CompareTo(this._innerList[right].Item);
if (x > 0 || (x == 0 && this._innerList[right].Index < this._innerList[best].Index)) best = right;
}
if(best != current) this.SwitchElements(best, current);
}
}
/// ---------------------------------------------------------------------------------
/// <summary>
/// Switch two elements
/// </summary>
/// <param name="item1"> The first element. </param>
/// <param name="item2"> The second element. </param>
/// ---------------------------------------------------------------------------------
private void SwitchElements(int item1, int item2)
{
InnerItem item = this._innerList[item1];
this._innerList[item1] = this._innerList[item2];
this._innerList[item2] = item;
}
/// ---------------------------------------------------------------------------------
/// <summary>
/// Hold the element (add an index to keep FIFO order with same keys).
/// </summary>
/// ---------------------------------------------------------------------------------
private class InnerItem
{
private T _item = default(T);
private int _index = 0;
/// ---------------------------------------------------------------------------------
/// <summary>
/// Represents an item (a Node in the tree).
/// </summary>
/// <param name="index"> The index of the Node. </param>
/// <param name="item"> The item. </param>
/// ---------------------------------------------------------------------------------
public InnerItem(int index, T item)
{
this._index = index;
this._item = item;
}
/// ---------------------------------------------------------------------------------
/// <summary>
/// Get or set the item.
/// </summary>
/// ---------------------------------------------------------------------------------
public T Item
{
get { return this._item; }
set { this._item = value; }
}
/// ---------------------------------------------------------------------------------
/// <summary>
/// Get or set the index of the item.
/// </summary>
/// ---------------------------------------------------------------------------------
public int Index
{
get { return this._index; }
set { this._index = value; }
}
}
}
}
Vous n'êtes pas encore membre ?
inscrivez-vous, c'est gratuit et ça prend moins d'une minute !
Les membres obtiennent plus de réponses que les utilisateurs anonymes.
Le fait d'être membre vous permet d'avoir un suivi détaillé de vos demandes et codes sources.
Le fait d'être membre vous permet d'avoir des options supplémentaires.