Better PriorityQueue

I've started to look over Julian Bucknall's site. I noticed that he had an update to his original priority queue problem:

Recently, my brother-in-law, who programs in VB.NET, needed a priority queue that also had some behaviors of a normal queue: dequeue should remove the highest priority item as usual, but if there were two or more objects with the same priority, they should be removed in arrival order (also known as FIFO or first-in-first-out order). The normal heap implementation of a priority queue could not do that since it takes no account of arrival order; the only ordering is by priority and if there were several items with the same priority, they'd be returned in some non-deterministic order.

From this, Julian ended up implementing an array of queues, one queue per second order sorting requirement. In this case, there was one array each of high, medium, and low priorities and they are each ordered by arrival time. Dequeueing removes from the high priority queue first until it is empty, and then from the medium, and then from the low.

But it seemed to me that he could have kept his PriorityQueue and just templatized on the priority, turning it from an int to an IComparable-derived object. So I decided to make the changes in my generic PriorityQueue<T> class:

1. Add template on key
   

   This:

   class PriorityQueue<T>

   becomes this:

   class PriorityQueue<T, K>
       where K: IComparable
   

2. Change struct Pair
   

   This:

   struct Pair
   {
      T val;
       int priority;
       public Pair(T v, int p)
       {
           this.val = v;
           this.priority = p;
       }
       public T Val { get { return this.val; } }
       public int Priority { get { return this.priority; } }
   }

   becomes this:

   struct Pair
   {
       T val;
       K priority;
       public Pair(T v, K p)
       {
           this.val = v;
           this.priority = p;
       }
       public T Val { get { return this.val; } }
       public K Priority { get { return this.priority; } }
   }

3. Change Enqueue
   

   This:

   public void Enqueue(T val, int priority)
   

   becomes this:

   public void Enqueue(T val, K priority)
   

4. Change ParentIsLowerPriority
   

   Change this:

   private static bool ParentIsLowerPriority(
       Pair parent, Pair item)
   {
       return (parent.Priority < item.Priority);
   }

   to this:

   private static bool ParentIsLowerPriority(
       Pair parent, Pair item)
   {
       return parent.Priority.CompareTo(item.Priority) < 0;
   }

5. Create LeftChildIsLowerPriority [refactoring]
   

   Create this:

   private static bool LeftChildIsLowerPriority(
       Pair leftChild, Pair rightChild)
   {
       K lp = leftChild.Priority;
       K rp = rightChild.Priority;
       return lp.CompareTo(rp) < 0;
   }

   Change this code:

   bool rightChildIsHigherPriority = 
       (array[child].Priority < array[child + 1].Priority);
   

   to this:

   bool rightChildIsHigherPriority = 
       LeftChildIsLowerPriority(array[child], 
           array[child + 1]);
   

[Download ZIP file] [PriorityQueue.cs]