Previous instalments
General Data Structures
Trees
The Priority Queue data structure has the same basic behaviour and operations as the classic queue found in .NET. A queue applies a first-in, first-out (FIFO) approach to a list of objects. This data structure is typically used in message processing to process messages in order of arrival. Queue implementations tend to have the following operations available :
- Enqueue - Adds the object at the back of the queue.
- Dequeue - Fetches and removes the object at the front of the queue.
- Peek - Fetches the object at the front of the queue for inspection without removing it.
- IsEmpty - Provides information on whether the queue contains any items.
- Count - The number of items in the queue.
A priority queue still retains queue semantics, but orders items with relation to their priority - that is, in a Min Priority Queue, the item with the lowest priority will always be at the head of the queue, while items in a Max Priority Queue will sort items in such a way that the item with the highest priority will be at the head. To illustrate, take the medical Triage system for applying priority to the treatment of patients (copied directly from Wikipedia) :
- Immediate: The casualty requires immediate medical attention and will not survive if not seen soon. Any compromise to the casualty’s respiration, haemorrhage control, or shock control could be fatal.
- Delayed: The casualty requires medical attention within 6 hours. Injuries are potentially life-threatening, but can wait until the Immediate casualties are stabilized and evacuated.
- Minimal: “Walking wounded,” the casualty requires medical attention when all higher priority patients have been evacuated, and may not require stabilization or monitoring.
- Expectant: The casualty is expected not to reach higher medical support alive without compromising the treatment of higher priority patients. Care should not be abandoned, spare any remaining time and resources after Immediate and Delayed patients have been treated.
We can define these classes of priority as a Java style enumeration :
public class Triage : IComparable<Triage> {
// "Constant" values
public static readonly Triage Green = new Triage(1);
public static readonly Triage Yellow = new Triage(2);
public static readonly Triage Red = new Triage(3);
// Triage Implementation
public Triage(int value)
{
Value = value;
}
public int Value { get; private set; }
// IComparable Members
public int CompareTo(Triage other) {
if (other == null)
{
throw new ArgumentNullException("other");
}
return Value.CompareTo(other.Value);
}
}
Using a priority queue we can trivially ordering of patients using the Triage value:
var queue = new PriorityQueue(PriorityQueueType.Maximum);
queue.Enqueue(new Patient("P1"), Triage.Red);
queue.Enqueue(new Patient("P2"), Triage.Green);
queue.Enqueue(new Patient("P3"), Triage.Green);
queue.Enqueue(new Patient("P4"), Triage.Yellow);
Running the code above will result in a priority queue that looks like this :
The priority queue will insert any new patients in their appropriate spot, much like the behaviour of a Sorted List. Inserting another critical patient (Red), will result in the following state :
Note that items follow chronological order when their priorities are equal. Retrieving the next patient is as simple as calling the Dequeue method on the queue. The Dequeue operation removes the item at the head of the queue:
Triage priority;
Patient criticalPatient = queue.Dequeue(out priority);
Console.WriteLine(criticalPatient.Name); // P1
Console.WriteLine(priority.Value); // 3 (Red)
Typically, priority queues are typically implemented using a heap or a self-balancing tree. The implementation in NGenerics uses a Red-black tree which makes the operations perform at O(log n).
Photo by Charles Deluvio 🇵🇭🇨🇦 on Unsplash