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
`Insert`

method that adds an item to the heap. - A
`RemoveRoot`

method that removes and returns the root item (minimum or maximum, depending on the heap type) from the heap. - A
`Peek`

method that returns but does not remove the root item. - A
`Count`

property that returns the number of items currently contained in the heap. - A
`Clear`

method that quickly removes all items from the heap. -
A method called

`GetConsumingEnumerable`

that 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 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.