A priority queue in C# - part 2
In my last post I had created a simple priority queue. Unfortunately it would sort itself each time an item is popped/dequeued. I have created a better priority queue that only sorts itself when the indexed value is changed.
I do this by having items implement the provided IPrioritizable interface. I was initially going to build it on the INotifyPropertyChanged interface but I thought this solution was simpler. The interface has 2 methods to Add/Remove an Action that notifies the PriorityQueue that it needs to be sorted. It now also requires a IComparer be provided. An example of this would be:
using System;
using System.Collections.Generic;
namespace PriorityQueueCollection.Tests
{
public class PrioritizableItem : IPrioritizable
{
private Action _indexUpdated;
private int _value;
public int Value
{
get { return _value; }
set
{
_indexUpdated();
_value = value;
}
}
public PrioritizableItem(int value)
{
_indexUpdated = () => { };
Value = value;
}
public void AddIndexUpdatedAction(Action indexUpdated)
{
_indexUpdated = indexUpdated;
}
public void RemoveIndexUpdatedAction()
{
_indexUpdated = () => { };
}
}
public class ComparePrioritizableItem : IComparer<PrioritizableItem>
{
public int Compare(PrioritizableItem x, PrioritizableItem y)
{
if (x.Value > y.Value)
{
return 1;
}
if (x.Value < y.Value)
{
return -1;
}
return 0;
}
}
}
Whilst not as simple as it’s predecessor it wastes less time ordering the queue on sequential pops.