It’s time to start designing the interface to our heap class. We already know in general what we want the heap to do: Insert, Remove, and Peek. But a useful .NET class needs a bit more.
Because I’ll be creating other heap types, I elected to define an interface that describes the minimum functionality I expect from a heap. Those properties and methods I expect are:
- An
Insertmethod that adds an item to the heap. - A
RemoveRootmethod that removes and returns the root item (minimum or maximum, depending on the heap type) from the heap. - A
Peekmethod that returns but does not remove the root item. - A
Countproperty that returns the number of items currently contained in the heap. - A
Clearmethod that quickly removes all items from the heap. - A method called
GetConsumingEnumerablethat removes items from the heap in order. - This replaces a consuming loop. This code:
while (heap.Count != 0) { var i = heap.RemoveRoot(); DoSomething(i); }Becomes:foreach (var i in heap.GetConsumingEnumerable()) { DoSomething(i); }If that were the only benefit the method provided, I wouldn’t have included it. But it’s very useful to have a method that will return the items in order so that I can pass it to a LINQ method, or any other method that expects anIEnumerable<T>.
This last is basically a replacement for a typical consuming loop, which you might write like this:
while (heap.Count != 0)
{
var i = heap.RemoveRoot();
DoSomething(i);
}Instead, you write:
foreach (var i in heap.GetConsumingEnumerable())
{
DoSomething(i);
}It’s very useful to have a method that will remove the items in order so that I can pass it to a LINQ method, or any other method that expects an IEnumerable<T>.
In addition, heaps are expected to implement IEnumerable<T> so that all of the Enumerable methods (i.e. LINQ) will work. Implementations of GetEnumerator are not consuming.
I gave a lot of thought to whether or not a heap should even implement IEnumerable<T>. The argument against doing so is that enumerating a heap without consuming is not a “normal” thing to do. But then, the Stack<T> and Queue<T> classes implement that interface even though enumerating those data structures is not a typical operation.
Once I decided that the heap should implement IEnumerable<T>, I had to decide whether enumerating the collection would return the items in sorted order (i.e. in ascending order for a Min-heap) or if it should just return the items in the order they’re stored in the underlying array. Returning them in ascending order is nice, but expensive; it would require O(n log n) time and O(n) extra space. Returning them in array order is simple: O(n) time with no extra space required. I elected to implement the latter, figuring that if you just want to know what’s on the heap then getting the list in any order is fine. If you want it in order, then use the appropriate LINQ method to order the items.
I had initially included an IsEmpty property that returns True if there are no items in the heap. But that’s really just a convenience function so that I can write if (!heap.IsEmpty) rather than if (heap.Count != 0). I believe that interfaces should be “complete but minimal,” and in this case there was little benefit to adding that convenience function when the equivalent functionality already exists. Users who want IsEmpty can write an extension method.
I also had included an InsertRange method that clients could call to add multiple items in a single statement. So rather than:
foreach (var i in collection)
{
heap.Insert(i);
}They could write:
heap.InsertRange(collection);Again, I elected to eliminate that method because it doesn’t add a huge benefit. It’s easy enough to write the code, and specific heap implementations can add an InsertRange method if they wish, just as List<T>, which implements IList<T>, defines its own AddRange method.
The result is a minimal but complete IHeap class:
public interface IHeap<T>: IEnumerable<T>
{
int Count { get; }
void Clear();
IEnumerable<T> GetConsumingEnumerable();
void Insert(T item);
T Peek();
T RemoveRoot();
}Classes that implement IHeap<T> will of course have a little more functionality than that, constructors in particular, but this is the bare minimum functionality we’ll expect from a heap class.
Next time we’ll look at the bare bones of the DHeap<T> base class and the MinDHeap<T> and MaxDHeap<T> derived classes with their constructors. After that, I’ll provide a full d-heap implementation so that we can put it through its paces.
