Many years ago I worked for an alarm monitoring company. It was our job to monitor home and business security systems and take action on the various signals. There are many different types of signals, but they generally fall into these broad categories:

• Test signals typically occur once per day just to let us know that the system is working.
• Trouble signals notify us of something wrong with the system: lost power or a sensor that's misbehaving, for example.
• Alert signals indicate a possible security breach: a broken window or the alarm not reset after the homeowner enters the house.
• Fire signals are usually from smoke alarms connected to the panel.
• Panic signals are from home or business owners who press the panic button on the panel.

I listed the signal categories in increasing order of priority. Obviously, a Fire signal is much more important than a Test signal, and if those two signals came in at the same time we would want to handle the Fire signal first. During busy times, the call center can get hundreds of signals per minute. Most of them are very low priority and can be handled routinely in the order in which they're received. But it's imperative that high priority signals come to the front of the processing queue so that they can be handled immediately.

Handling alarm signals of differing priorities is an application that just begs for a priority queue (http://en.wikipedia.org/wiki/Priority_queue). The priority queue data structure supports, the following operations:

enqueue - add an item and associated priority to the queue

dequeue - remove from the queue the element that has the highest priority

peek - examine the highest priority element without removing it from the queue

You might notice that these are the same three operations that are usually implemented for a first-in, first-out (FIFO) queue, the only difference being that items are removed in order of priority rather than in the order they were inserted. In fact, you could implement a FIFO queue using a priority queue if you used the insertion time as the priority value and reversed the priority test so that the earliest insertion time was given the highest priority. Doing so would be quite inefficient, of course, but it shows that a FIFO queue is really just a specialized priority queue.

Priority Queue Implementations

There are many different ways to implement priority queues. The easiest method would be to create a linked list of items kept in descending priority order. Inserting an item into the queue would require that you walk the list looking for the insertion point. Removing the highest priority item would be very fast--just take the first item from the list. This implementation would be sufficient for a very small (maybe a few hundred items) queue. The average time taken to insert an item into the queue grows linearly with the size of the queue. If you have a large queue that is updated frequently, you'll spend a lot of time walking the list.

If you have a relatively small number of discrete priority values, as in the case of alarm signals, you can implement the priority queue by creating one list for each of the priority levels. To insert an item, you add it to the end of the list for that priority level. A Trouble signal, for example, would be added to the end of the Trouble list. To remove the highest priority item, you start with the highest priority value to see if it contains any items. If so, you remove the item. Otherwise you continue to the next priority level. If you have discrete priority values, insertion (enqueue) and removal (dequeue) take constant time.

Very often, though, an item's priority is expressed as a floating point number: often a number between 0 and 1 that indicates a probability. One such application would be in decision tree searching where the many possible paths are assigned probabilities based on the likelihood of the path being productive. When your priority values are floating point numbers (or a wide range of integers), you need a generalized way to efficiently enqueue and dequeue items.

One popular data structure for implementing priority queues is a binary heap (http://en.wikipedia.org/wiki/Binary_heap), which is an ordered (but not sorted) and balanced binary tree. The nature of the heap makes it ideal for representing a priority queue:

• Because the tree is always balanced, item insertion and removal takes time proportional to the log (base 2) of the number of items in the tree.
• The heap property says that the value at each node is greater than or equal to the value of each of its children. The item with the highest value is always at the root of the tree.

The rest of this article details the construction of a generic binary heap priority queue collection class in C#.