Signum Framework Logo
"Open framework that encourages convention over configuration, using C# code,
not XML files, to model at the right level of abstraction and achieve deadlines.
...but also has a full Linq provider, and syncs the schema for you!"
Login
RSS

Search

»



Main
Index
Map
Videos
Download
Source code
Tutorials
Forum
FAQ



Image



PoweredBy

Data Structures - PriorityQueue

RSS
Modified on 2009/03/29 04:58 by helen Categorized as Uncategorized

PriorityQueue

A priority queue is a data structure similar to a queue, but where every element has priority associated. At any given moment the object with less (or most) priority is retrieved.

It's usually implemented using a heap. Our version, based on the work of BenDi, uses a binary heap in a flat List, and instead of setting priority explicitly for each element we use IComparable<T> interface of Comparison<T> delegate. Let's see what it looks like!

public class PriorityQueue<T>
{
    List<T> list = new List<T>(); //where the elements are actually stored
    Comparison<T> comparer; //The comparison delegate used internally
    
    //Default constructor, returns default comparator for a T that implements IComparable
    public PriorityQueue():this(Comparer<T>.Default.Compare) 
    //Constructor with explicit IComparer (Think about using LambdaComparer)
    public PriorityQueue(IComparer<T> comparer) 
    //Constructor with explicit Comparisor
    public PriorityQueue(Comparison<T> comparer)

public int Count{get;} // number of elements in the queue public bool Empty{get;} //returns true if no element is in the queue

public int Push(T element) //Enqueue an element public void PushAll(IEnumerable<T> elements) //Enqueue all the elements public T Pop() //Dequeue and returns the smallest element public T Peek() //Returns the smallest element without dequeuing //Forces a position update of an element already in the queue //Useful if its' comparison value has changed some how public void Update(T element)

public bool Contains(T element) //returns true if element is in the queue public void Clear() //Removes all the elements in the queue }


Example:

PriorityQueue<int> numbers = new PriorityQueue<int>(); 
numbers.Push(1);
numbers.Push(10);
numbers.Push(8);
numbers.Push(12);
numbers.Push(4);
numbers.Push(54);

while (!numbers.Empty) Console.Write(numbers.Pop() + ", ");

//Writes: 1, 4, 8, 10, 12, 54,

Example using an explicit IComparer (LambdaComparer):

PriorityQueue<string> numbers = new PriorityQueue<string>(new LambdaComparer<string, int>(s => s.Length));
numbers.Push("Teutons");
numbers.Push("Mongols");
numbers.Push("Persians");
numbers.Push("Sarracens");
numbers.Push("Goths");
numbers.Push("Japanese");
numbers.Push("Celts");
numbers.Push("Chinese");
numbers.Push("Wikings");
numbers.Push("Britons");
numbers.Push("Turks");
numbers.Push("Franks");
numbers.Push("Byzantines");

while (!numbers.Empty) Console.WriteLine(numbers.Pop());

//Goths //Turks //Celts //Franks //Britons //Chinese //Vikings //Teutons //Mongols //Persians //Japanese //Sarracens //Byzantines

Note that, in the current implementation, the priority is the only information taken into account, not the order they where introduced.
Creative Commons License Signum Framework Site by Signum Software is licensed under a Creative Commons Attribution 3.0 License.
Powered by ScrewTurn Wiki version 3.0.5.600.