Tuesday, February 17, 2009

C# PriorityQueue<T> Implementation

Before I get any more abusive comments. This post is targeted at the 2.0 version of the Framework.

Guess I could of just used a SortedList<T1, T2> implementation in System.Collections.Generic, but I want a PriorityQueue<T>. So here goes.

public class PriorityQueue<T> : SortedList<T, T>
{
public PriorityQueue()
: base()
{
}

public PriorityQueue(IComparer<T> comparer)
: base(comparer)
{
}

//
// Summary:
// Returns the object at the beginning of the System.Collections.Generic.Queue<T>
// without removing it.
//
// Returns:
// The object at the beginning of the System.Collections.Generic.Queue<T>.
//
// Exceptions:
// System.InvalidOperationException:
// The System.Collections.Generic.Queue<T> is empty.
public T Peek()
{
return this.Last().Key;
}

//
// Summary:
// Removes and returns the object at the beginning of the System.Collections.Generic.Queue<T>.
//
// Returns:
// The object that is removed from the beginning of the System.Collections.Generic.Queue<T>.
//
// Exceptions:
// System.InvalidOperationException:
// The System.Collections.Generic.Queue<T> is empty.
public T Dequeue()
{
T item = this.Last().Key;
this.RemoveAt(this.Count - 1);
return item;
}

//
// Summary:
// Adds an object to the end of the System.Collections.Generic.Queue<T>.
//
// Parameters:
// item:
// The object to add to the System.Collections.Generic.Queue<T>. The value can
// be null for reference types.
public void Enqueue(T item)
{
this.Add(item, item);
}
}

4 comments:

  1. This is not a priority queue, it is a queue...
    where is the code ? where is the sorting? where are the member?

    ReplyDelete
  2. Thr sorting is enclosed in the SortedList base class. Do your reading before posting.

    ReplyDelete
  3. My Bad I should of mentioned this post was for DotNet Framework 2.0

    ReplyDelete
  4. this one doesn't work for objects with duplicate priority keys.

    ReplyDelete