Deciding on an Interface

One of the most difficult parts of writing reusable code is deciding what features to include and, more importantly, what to leave out. The best advice I ever got in this area was from somebody who told me to strive for interfaces that are complete but minimal. That is, they do everything required and nothing extraneous. Fortunately, I have the .NET Framework's existing collection classes to use as a model, and I based my class's interface on the interface to the generic System.Collections.Generic.Queue collection class.

One major difference between my PriorityQueue class and the .NET generic Queue is that I have to store a priority value with each item. Although I could enforce the constraint that any items to be placed in the PriorityQueue implement a particular interface (something like IPriority, for example), I think such a constraint in a generalized collection class is burdensome. As a result, the items that actually go into the priority queue are of type PriorityQueueItem. These items are used in much the same way as the generic LinkedList uses LinkedListNode objects and the way that Dictionary uses KeyValuePair structures. The PriorityQueueItem structure is defined as:

public struct PriorityQueueItem<TValue, TPriority>
{
    private TValue value;
    private TPriority priority;

    public PriorityQueueItem(TValue val, TPriority pri)
    {
        this.value = val;
        this.priority = pri;
    }

    /// <summary>
    /// Gets the value of this PriorityQueueItem.
    /// </summary>
    public TValue Value
    {
        get { return value; }
    }

    /// <summary>
    /// Gets the priority associated with this PriorityQueueItem.
    /// </summary>
    public TPriority Priority
    {
        get { return priority; }
    }
}

With the generic FIFO Queue as a model, coming up with the PriorityQueue interface wasn't too hard. With the exception of the constructors (discussed later), the interface is quite similar. PriorityQueue implements the following public properties.

Capacity gets or sets the queue's capacity--the number of items that it can hold. The capacity doesn't prevent the queue from holding more items. Rather, it pre-allocates space for items, or allows you to shrink allocated space when the number of items in the queue is small. An argument can be made for not exposing this property and letting the internals manage memory as required. That's what Queue does. However, I've found the Capacity property to be useful in the other collection classes, so included it here.

Count returns the number of items that are currently in the priority queue. This property is read-only.

For the most part, the methods exposed in the public interface mimic the methods exposed by the generic Queue collection class.

Clear removes all objects from the queue and resets the capacity to the default minimum capacity.

Contains determines whether an item is in the queue.

CopyTo copies the queue elements to a one-dimensional array.

Dequeue removes the highest priority item from the queue and returns it. The returned item is a typed PriorityQueueItem that contains a reference to the queued item and its associated priority.

Enqueue adds an item and its associated priority to the queue.

GetEnumerator returns an enumerator that iterates through the queue. Note that iterating through the items will not be done in priority order. The only guarantee is that the first item encountered will be the highest priority item.

Peek returns the highest priority item from the queue and returns it. The item is not removed from the queue. The return value is the same as for Dequeue.

Remove removes the item with the given value from the queue. An overload allows you to specify the IEqualityComparer interface that will be used for item equality comparisons.

ToArray copies the queued items to a new array of PriorityQueueItem objects. The only guarantee about the order of items in the array is that the first item will have the highest priority.

TrimExcess Sets the capacity to the actual number of elements in the queue, if that number is less than 90 percent of current capacity.

I had a difficult time deciding how flexible to make the class when it came to comparing the priorities. At first I was going to require that items inserted into the queue contain the priority and implement the IComparer interface for comparing priorities. That's a heavy restriction to put on a client class, though, and would force clients to implement wrappers around classes for which they didn't have source.

I finally settled on a comparison interface similar to what's by the generic List collection class when sorting. The default behavior is to use the IComparer interface implementation in the priority type. That makes it simple to use numbers, strings, and other common types as priority keys. If the priority type doesn't implement IComparer or you want a different comparison (reverse order, for example), you can specify an object that implements IComparer, or you can pass a reference to a Comparison delegate for the given type.

All that flexibility resulted in six different constructors:

/// <summary>
/// Initializes a new instance of the PriorityQueue class that is empty,
/// has the default initial capacity, and uses the default IComparer.
/// </summary>
public PriorityQueue()

/// <summary>
/// Initializes a new instance of the PriorityQueue class that is empty,
/// has the specified initial capacity, and uses the default IComparer.
/// </summary>
/// <param name="initialCapacity">Desired initial capacity.</param>
public PriorityQueue(Int32 initialCapacity)

/// <summary>
/// Initializes a new instance of the PriorityQueue class that is empty,
/// has the default initial capacity, and uses the specified IComparer.
/// </summary>
/// <param name="comparer">An object that implements the IComparer interface
/// for items of type TPriority.</param>
public PriorityQueue(IComparer<TPriority> comparer)

/// <summary>
/// Initializes a new instance of the PriorityQueue class that is empty,
/// has the specified initial capacity, and uses the specified IComparer.
/// </summary>
/// <param name="initialCapacity">Desired initial capacity.</param>
/// <param name="comparer">An object that implements the IComparer interface
/// for items of type TPriority.</param>
public PriorityQueue(int initialCapacity, IComparer<TPriority> comparer)

/// <summary>
/// Initializes a new instance of the PriorityQueue class that is empty,
/// has the default initial capacity, and uses the specified comparison
/// function for comparing items of type TPriority.
/// </summary>
/// <param name="comparison">The comparison function.</param>
public PriorityQueue(Comparison<TPriority> comparison)

/// <summary>
/// Initializes a new instance of the PriorityQueue class that is empty,
/// has the specified initial capacity, and uses the specified comparison
/// function for comparing items of type TPriority.
/// </summary>
/// <param name="initialCapacity">The desired initial capacity.</param>
/// <param name="comparison">The comparison function.</param>
public PriorityQueue(int initialCapacity, Comparison<TPriority> comparison)

Given that interface, actually implementing the PriorityQueue class was straightforward. I cribbed some old Pascal binary heap code and converted it to C# for the heap management. That made up the two workhorse methods: Enqueue and RemoveAt (called by Dequeue and Remove). Everything else in the class is simply there to implement the collection semantics: copying and iterating through items, managing the capacity, and constructing the thing.

Of the 500 lines that make up the PriorityQueue class, a very small amount--less than 50 lines, including comments--has anything to do with the actual binary heap. I've found this to be true in many other classes that I've built. The actual work is done by a small amount of code. The rest of the code is there to make it possible for the work to be done in a generalized manner.