Continuing with my implementation of a D-ary heap, after a rather long break during which I was busy with other things . . .
The hardest part of implementing the DHeap class was getting the constructors right. Once those are right, the rest of the class just falls into place. The constructors were difficult because there are four different parameters that control construction, and I wanted to avoid having to create a different constructor for every possible combination of parameters. With a little thought and judicious use of default parameters, I was able to do everything with three constructors: one private and two protected.
Internally, the DHeap class depends on four fields:
// Heap item comparer
private readonly IComparer<T> _comparer;
// Result comparer (for Min-heap and Max-heap)
private readonly Func<int, bool> _resultComparer;
// Number of children for each node.
private readonly int _ary;
// List that holds the heap items
private readonly List<T> _items;
I used List<T> here rather than an array (i.e. T[]) to take advantage of the automatic growth that the List class provides. I could have implemented my own dynamic array and saved a few cycles, but the slight performance gain really isn’t worth the extra effort.
The _comparer is an IComparer<T> implementation that compares two items. Clients can pass a custom comparer if their type doesn’t implement IComparable<T>, or if they want to compare items differently than the default comparer does. If no custom comparer is supplied, the constructors will use Comparer<T>.Default.
We discussed the _resultComparer in a previous post. It’s there so that we can use the same code for a Min-heap and for a Max-heap. The MinDHeap<T> and MaxDHeap<T> derived classes pass the appropriate comparison function as a parameter to the constructor.
The _ary property determines the “arity” of the heap. Passing 2 will create a binary heap, passing 4 will create a 4-heap, etc.
The constructors allow the client to supply values for _comparer, _ary, and _resultComparer. In addition, clients can specify a capacity, which determines the initial capacity of the heap. Doing so prevents unnecessary reallocations in the same way that the initialCapacity parameter to the List constructor works.
Given that, the class with its constructors and internal fields looks like this:
[DebuggerDisplay("Count = {Count}")]
public class DHeap<T>: IHeap<T>
{
private readonly IComparer<T> _comparer;
private readonly Func<int, bool> _resultComparer;
private readonly int _ary;
private readonly List<T> _items = new List<T>();
private DHeap(int ary, Func<int, bool> resultComparer,
IComparer<T> comparer = null)
{
_ary = ary;
_comparer = comparer ?? Comparer<T>.Default;
_resultComparer = resultComparer;
}
internal DHeap(int ary, Func<int, bool> resultComparer, int capacity,
IComparer<T> comparer = null)
: this(ary, resultComparer, comparer)
{
if (ary < 2)
{
throw new ArgumentOutOfRangeException("ary",
"must be greater than or equal to two.");
}
if (capacity < 0)
{
throw new ArgumentOutOfRangeException("capacity",
"must be greater than zero.");
}
_items = new List<T>(capacity);
}
internal DHeap(int ary, Func<int, bool> resultComparer,
IEnumerable<T> collection, IComparer<T> comparer = null)
: this(ary, resultComparer, comparer)
{
if (ary < 2)
{
throw new ArgumentOutOfRangeException("ary",
"must be greater than or equal to two.");
}
if (collection == null)
{
throw new ArgumentNullException("collection",
"may not be null.");
}
_items = new List<T>(collection);
Heapify();
}
}
DHeap<T> is a base class that is intended to be used only by the MinDHeap<T> and MaxDHeap<T> derived classes. The private constructor sets the common properties from supplied parameters, and the two protected constructors are called by the derived class’s constructors. Because there are no public constructors, no other classes can derive from this one.
I considered making the constructors public so that any client could derive from this class, but doing so would necessitate making most of the methods virtual, and the private fields protected so that derived classes could manipulate them. But if a derived class wanted to override, say, Insert, it would likely be changing almost all of the implementation. At that point, is it really a derived class or a new class entirely? It seemed more reasonable to provide the IHeap<T> interface for those who want to create a different type of heap.
The ary and resultComparer parameters are common to both of the accessible constructors, and must be specified. The comparer parameter also is common to both, but it can be defaulted (i.e. not supplied). The only real difference between the two constructors is that one takes an initial capacity and the other takes a collection from which the heap is initialized. Both constructors call the private constructor to set the common values, and then initialize the heap.
Clients don’t create instances of DHeap<T>. Instead, they create instances of MinDHeap<T> and MaxDHeap<T>. Those classes each consist of a static comparison function (the result comparer) and three constructors that simply chain to the DHeap<T> constructors.
public class MinDHeap<T> : DHeap<T>
{
[MethodImpl(MethodImplOptions.AggressiveInlining)]
static private bool MinCompare(int r)
{
return r > 0;
}
/// <summary>
/// Initializes a new instance that is empty
/// and has the specified initial capacity.
/// </summary>
public MinDHeap(int ary, int capacity, IComparer<T> comparer = null)
: base(ary, MinCompare, capacity, comparer)
{
}
/// <summary>
/// Initializes a new instance that is empty
/// and has the default initial capacity.
/// </summary>
public MinDHeap(int ary, IComparer<T> comparer = null)
: this(ary, 0, comparer)
{
}
/// <summary>
/// Initializes a new instance that contains
/// elements copied from the specified collection.
/// </summary>
public MinDHeap(int ary, IEnumerable<T> collection,
IComparer<T> comparer = null)
: base(ary, MinCompare, collection, comparer)
{
}
}
public class MaxDHeap<T> : DHeap<T>
{
[MethodImpl(MethodImplOptions.AggressiveInlining)]
static private bool MaxCompare(int r)
{
return r < 0;
}
/// <summary>
/// Initializes a new instance that is empty
/// and has the specified initial capacity.
public MaxDHeap(int ary, int capacity, IComparer<T> comparer = null)
: base(ary, MaxCompare, capacity, comparer)
{
}
/// <summary>
/// Initializes a new instance that is empty
/// and has the default initial capacity.
/// </summary>
public MaxDHeap(int ary, IComparer<T> comparer = null)
: this(ary, 0, comparer)
{
}
/// <summary>
/// Initializes a new instance that contains
/// elements copied from the specified collection.
/// </summary>
public MaxDHeap(int ary, IEnumerable<T> collection, IComparer<T> comparer = null)
: base(ary, MaxCompare, collection, comparer)
{
}
}
I marked the result comparison methods (MinCompare and MaxCompare) with an attribute that tells the compiler to inline them aggressively. Considering that comparison is what determines how fast the heap runs, it pays to make those comparisons as inexpensive as possible, within certain limits. Adding the attribute provides a measurable performance gain at very little cost in code size or complexity.
Clients that want to create a binary Min-heap of integers can write:
var myHeap = new MinDHeap(2);
To create a trinary Max-heap of some custom type, using a custom comparison function:
var myHeap = new MaxDHeap(3, 1000, new CustomComparer());
That assumes, of course, that somewhere there is a class called CustomComparer that implements IComparable<MyType>.
Next time I’ll complete implementation of the DHeap<T> class and give you a link to where you can download the code and some examples.
