Priority Queues with C#

In the November 2012 issue of Visual Studio Magazine, I wrote a short technical article titled “Priority Queues with C#”. See http://visualstudiomagazine.com/articles/2012/11/01/priority-queues-with-c.aspx. A priority queue is a data structure where each item stored has some kind of priority value and items are stored so that the item with the highest priority is always at the front of the queue.

The idea is that you could implement such a data structure using a sorted list or a binary search tree: after every add (enqueue) or remove (dequeue), you’d just resort the data structure. But this involves unnecessary work because for a priority queue you only care about the priority of the front item. So, a priority queue implemented using what is called a binary heap instead of a list or a tree can give best performance.

Priority queues are relatively rarely used. I come across them most often when working with graph shortest path algorithms.