Kategori Computer Science

How to design a Priority Queue in C#

What is a Priority Queue?

To be a bit formal, a priority queue is an abstract data type (ADT), similar to a regular queue, but where each element has a priority associated to it. An element with high priority is served before an element with a low priority. Elements which have the same priority are usually served in the order they were added, but that is not a formal requirement.

In other words, it’s like the queue to the fancy club down town, where all we regular people have to stay in line outside and the VIPs just walks right in.

Choosing the internal collection type

Since we are designing a queue, we want a method for Enqueuing elements and a method for Dequeuing elements. Somehow we need to keep track of the elements that are in the queue and the straight forward way to do this is to use a Collection type. One commonly used Collection type that supports both adding and removing elements is the generic List<T> from the System.Collections.Generic namespace. Sounds like a good fit? Yes! Let’s write some code:

public class PriorityQueue<T>
{
  private readonly List<T> _pq = new List<T>();
}

Making sure enqueued elements can be prioritized

In order to know which element that has the highest priority we need to be able to prioritize one against the other in some way. But how can we put such restrictions on the elements from within the PriorityQueue class? Fortunately there is a way in C# to put constraints on generic types (in our case our generic type is T). We can do this by informing the compiler that objects of type T must be comparable to each other so they can be sorted, in other words, T must implement IComparable (part of the .NET framework). Let’s add that restriction to our PriorityQueue:

public class PriorityQueue<T> where T : IComparable<T>
{
  private readonly List<T> _pq = new List<T>();
}

Enqueuing and Dequeuing elements

A queue is useless if you can’t enqueue and dequeue items from it. It will get a bit tricky here in a while when we will need to ensure elements are added in the right position in regards to priority, but let’s start with something simple. Let’s pretend that we don’t care about priority and just want a regular queue. This can be achieved by adding elements to the end of the List and removing them at the beginning:

public class PriorityQueue<T> where T : IComparable<T>
{
  private readonly List<T> _pq = new List<T>();
  
  public void Enqueue(T item)
  {
    _pq.Add(item);
  }

  public T Dequeue()
  {
    var item = _pq[0];
    _pq.RemoveAt(0);
  
    return item;
  }
}

Cool, now we have a regular queue, but how do we ensure we always Dequeue the top prioritized item? One way we could do that is to sort the items after each time we add a new item:

public class PriorityQueue<T> where T : IComparable<T>
{
  private readonly List<T> _pq = new List<T>();
  
  public void Enqueue(T item)
  {
    _pq.Add(item);
    _pq.Sort();
  }

  public T Dequeue()
  {
    var item = _pq[0];
    _pq.RemoveAt(0);
    
    return item;
  }
}

This should work, and it’s a descent solution. However, sorting the List<T> like this every time an element is enqueued is not the optimal solution. We can do it better.

Making it scale

Now we have to dive into the realms of Computer Science. If concepts like Big O notation and Binary Heaps just are strange words that you don’t know what they mean I recommend reading up on those first and then returning here. You can find an introduction to Big O notation here and a good explanation of Binary Min and Max Heaps here.

All ready to go? Great! So, using the solution above we get an O(nlogn) dependency when Enqueuing elements, that is due to the sort that occurs after each addition. However, if we order the data in the List<T> as a Binary Min Heap both the Enqueue and Dequeue operations can be improved to O(logn) which scales much better.

I will not explain how the Insert and Delete operations work in detail in a Binary Min Heap. You can find a good explanation, with fancy animations, by following the link above. Instead, lets look at the resulting code:

public class PriorityQueue<T> where T : IComparable<T>
{
  private readonly List<T> _pq = new List<T>();

  public void Enqueue(T item)
  {
    _pq.Add(item);
    BubbleUp();
  }
  
  public T Dequeue()
  {
    var item = _pq[0];
    MoveLastItemToTheTop();
    SinkDown();
    return item;
  }

  private void BubbleUp() // Implementation of the Min Heap Bubble Up operation
  {
    var childIndex = _pq.Count - 1;
    while (childIndex > 0)
    {
      var parentIndex = (childIndex - 1) / 2;
      if (_pq[childIndex].CompareTo(_pq[parentIndex]) >= 0)
        break;
      Swap(childIndex, parentIndex);
      childIndex = parentIndex;
    }
  }

  private void MoveLastItemToTheTop()
  {
    var lastIndex = _pq.Count - 1;
    _pq[0] = _pq[lastIndex];
    _pq.RemoveAt(lastIndex);
  }

  private void SinkDown() // Implementation of the Min Heap Sink Down operation
  {
    var lastIndex = _pq.Count - 1;
    var parentIndex = 0;
    
    while (true)
    {
      var firstChildIndex = parentIndex * 2 + 1;
      if (firstChildIndex > lastIndex)
      {
        break;
      }
      var secondChildIndex = firstChildIndex + 1;
      if (secondChildIndex <= lastIndex && _pq[secondChildIndex].CompareTo(_pq[firstChildIndex]) < 0)
      {
        firstChildIndex = secondChildIndex;
      }
      if (_pq[parentIndex].CompareTo(_items[firstChildIndex]) < 0)
      {
        break;
      }
      Swap(parentIndex, firstChildIndex);
      parentIndex = firstChildIndex;
    }
  }

  private void Swap(int index1, int index2)
  {
    var tmp = _pq[index1];
    _pq[index1] = _pq[index2];
    _pq[index2] = tmp;
  }
}

There you have it! A fully working Priority Queue implementation in C# that scales.

You can find a, very similar but not quite identical, implementation on my GitHub page: https://github.com/Backhage/PriorityQueue

Book Review – The imposter’s handbook

Introduction

Just by reading the heading of this blog post won’t tell you anything about what kind of book I am writing a review on. The full title is actually The imposter’s Handbook – A CS Primer For Self-Taught Programmers, where CS is short for Computer Science.

The book is written by Rob Conery, a self-taught programmer without a CS degree. In 2014 Rob spent a year studying Computer Science fundamentals and wrote about the things he learned, which resulted in this book. When I heard the book being discussed on the Coding Blocks podcast I got interested and decided to order a copy of it for myself. Just like Rob I am (mostly) self-taught when it comes to Computer Science subjects. I do have a master’s degree, but in electrical engineering, so none of the courses I took on the University covered the subjects that Rob writes about.

CS subjects covered in the book

The book touches on many areas, and does not deep dive into any of them, so it is probably wrong to say that any of the subjects are ”covered”. However, the author introduces each subject and gives you enough understanding about them to cover the basics. And if you want to deep dive into anyone there are a lot of books out there that do cover the details.

Subjects discussed are:

  • Computation
  • Complexity
  • Lamdba Calculus
  • Machinery
  • Big O
  • Data Structures
  • Algorithms
  • Compilation
  • Software Design Patterns
  • Software Design Principles
  • Functional Programming
  • Databases
  • Testing
  • Essential Unix

As you understand, with these many subjects, you cannot dive into details and still have everything in a single book.

Is this book for me?

I would say that I depends. For me personally I enjoyed reading the first chapters, but from Big O and forward I pretty much already knew the things that the book brings up. However, I recognize that I am not the typical self-taught programmer. I read, a lot, of books on programming, I have taken Coursera courses on algorithms, and I do programming challenges on Codewars, Hackerrank, and Codility just for the fun of it, I listen to several programming podcasts, and subscribe to several programming newsletters. But if you look at the subjects listing above and feel that you don’t have a basic understanding on these subjects, this book is most certainly quite useful.

Rating

I would really like to give this book a high rating, since I know that the author has put a lot of effort into learning the things himself, as well as writing about them in a way that is useful for others. There are however some things that lowers the score. These are:

  • Not correctly formatted for print
    I have the printed version of the book, and it is obvious that the source needs to be looked over to avoid having pages where the last line on the page is a heading, and similar formatting errors.
  • Questionable code quality
    I found many of the code samples to be questionable in regards of code structure, naming of variables, etc. I expected the book to contain code samples that clearly showed the expected functionality.
  • Questionable text quality
    When I read a technical book I expect it have been proof read and reworked a couple of times. This book often feel more like an early draft than the finished book.

Taking the above into account I give this book a score of: 3/5. It can definitely be good to get a brief understand on some important CS subjects, but if you want to learn any of the subjects really well, I recommend complementing with some books from a well known publisher.

Links

The homepage for the Imposter’s handbook