Previous installments

General Data Structures

Trees

 

The Priority Queue data structure has the same basic behavior and operations as the classic queue found in .NET.   A queue applies a first-in, first-out (FIFO) approach to a list of objects, and is typically used in message processing where messages are processed in order of arrival. Queue implementations usually 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 an indication of 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 be sorted 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, hemorrhage 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 :

400: Invalid request

Using a priority queue, we can easily implement the ordering of patients :

400: Invalid request

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 behavior 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 currently at the head of the queue :

400: Invalid request

 

Typically,  priority queues are implemented using a heap or a self-balancing tree - the implementation in NGenerics is backed by  a Red-black tree, giving it's operations O(log n)  performance.