In this post I am sharing another code Kata: an implementation of a binary heap. Once we have the heap implemented, we will easily deduce a heap sort and a priority queue based on it. It takes about 100 lines of C# code.

Binary Heap

The heap tree is “threaded”: the tree nodes are stored in an array list provided in the constructor (line 6). For each element at index i: its left child is at index 2i+1, its right child is at 2i+2 and its parent is at (i−1)/2. These relations are respectively implemented in RightChild (line 80), LeftChild  (line 82) and Parent (line 78) methods.

If the provided list is not empty, it will be “heapified”. This is done using the Heapify method (line 40) and is similar to STL’s make_heap operation in C++.

New elements can be inserted to the heap using the Insert method (line 32). A new element will be first put at the end of the tree, then pulled up until the tree satisfies the heap property again. This operation is implemented in the HeapUp method (line 48).

The root element of the heap can be removed from the tree using the PopRoot method (line 16). The last element of the tree is then put at the root and pushed down until the tree satisfies the heap invariant. This is implemented using the HeapDown method (line 60).

public class Heap<T>
{
  private readonly IList<T> _list;
  private readonly IComparer<T> _comparer;

  public Heap(IList<T> list, int count, IComparer<T> comparer)
  {
    _comparer = comparer;
    _list = list;
    Count = count;
    Heapify();
  }

  public int Count { get; private set; }

  public T PopRoot()
  {
    if (Count == 0) throw new InvalidOperationException("Empty heap.");
    var root = _list[0];
    SwapCells(0, Count - 1);
    Count--;
    HeapDown(0);
    return root;
  }

  public T PeekRoot()
  {
    if (Count == 0) throw new InvalidOperationException("Empty heap.");
    return _list[0];
  }

  public void Insert(T e)
  {
    if (Count >= _list.Count) _list.Add(e);
    else _list[Count] = e;
    Count++;
    HeapUp(Count - 1);
  }

  private void Heapify()
  {
    for (int i = Parent(Count - 1); i >= 0; i--)
    {
      HeapDown(i);
    }
  }

  private void HeapUp(int i)
  {
    T elt = _list[i];
    while (true)
    {
      int parent = Parent(i);
      if (parent < 0 || _comparer.Compare(_list[parent], elt) > 0) break;
      SwapCells(i, parent);
      i = parent;
    }
  }

  private void HeapDown(int i)
  {
    while (true)
    {
      int lchild = LeftChild(i);
      if (lchild < 0) break;
      int rchild = RightChild(i);

      int child = rchild < 0
        ? lchild
        : _comparer.Compare(_list[lchild], _list[rchild]) > 0 ? lchild : rchild;

      if (_comparer.Compare(_list[child], _list[i]) < 0) break;
      SwapCells(i, child);
      i = child;
    }
  }

  private int Parent(int i) { return i <= 0 ? -1 : SafeIndex((i - 1) / 2); }

  private int RightChild(int i) { return SafeIndex(2 * i + 2); }

  private int LeftChild(int i) { return SafeIndex(2 * i + 1); }

  private int SafeIndex(int i) { return i < Count ? i : -1; }

  private void SwapCells(int i, int j)
  {
    T temp = _list[i];
    _list[i] = _list[j];
    _list[j] = temp;
  }
}

Quick Complexity Analysis

The complexity of HeapUp and HeapDown are bound by the depth of the (complete) tree. Hence, they have both a O(log(N)) complexity (where N is the number of elements in the heap). As a consequence, Insert and PopRoot have both the same complexity: O(log(N)).

PeekRoot doesn’t imply any structural changes and has a O(1) complexity.

The Heapify method has O(N) complexity; a detailed analysis is presented here. Therefore, constructing a heap with a non empty list of size count will cost O(count).

Heap Sort

The heap sort is quite straightforward given the binary heap above. We just build a heap with the input array, this is O(N), and then pop the root element from the heap until it is empty, this is N times O(log(N)). The presented heap sort here is done in-place, with O(1) space complexity and with O(N log(N)) worst case time complexity.

public class HeapSort<T>
{
  public static void Sort(IList<T> list, IComparer<T> comparer)
  {
    var heap = new Heap<T>(list, list.Count, comparer);
    while (heap.Count > 0)
    {
      heap.PopRoot();
    }
  }
}

Priority Queue

In fact the heap is a priority queue . We just need a wrapper (delegator) object to create the heap and the heap’s list. The code is self-explanatory.

public class PriorityQueue<T>
{
  private readonly Heap<T> _heap;

  public PriorityQueue(IComparer<T> comparer)
  {
    _heap = new Heap<T>(new List<T>(), 0, comparer);
  }

  public int Size { get { return _heap.Count; } }

  public T Top() { return _heap.PeekRoot(); }

  public void Push(T e) { _heap.Insert(e); }

  public T Pop() { return _heap.PopRoot(); }
}