A binary heap, as you recall, is just a binary tree that satisfies the heap property and the shape property. It’s a popular data structure because it works well, is reasonably efficient, and is easy to implement. But it’s not the only way to implement a heap. For example, consider a heap in which each node has three children:

This tree satisfies the heap property (each node is smaller than its child nodes), and it satisfies the shape property: all levels but the last are filled.

You could create a similar structure in which each node has four children:

Again, that tree satisfies both properties.

The binary heap is a special case of the more general d-ary heap, or d-heap. A heap with three children per node is called a 3-heap. Four children per node would be a 4-heap. The binary heap, of course, is a 2-heap. I suppose you could call a sorted list a 1-heap.

The rules for adding items to and removing items from a d-heap are exactly the same as for adding and removing in a binary heap.

• To remove an item, replace the root node with the last node in the heap and sift down.
• To add an item, add the item to the end of the heap and bubble up.

Finally, you can represent a d-heap in an array exactly as you can a binary heap. The formulae for finding a node’s children or parent are the same, with the single modification of replacing 2 with d. So the parent of node x in a d-heap is at position (x-1)/d. And the children are at [(x*d)+1, (x*d)+2, ... (x*d)+d].

The number of items in a full d-heap of n levels is (1-dn)/(1-d). A seven level binary heap contains 127 items. A seven-level 4-heap would contain 5,461 (16383/3) items.

A little algebra tells us that the number of levels required to hold n items in a d-heap is logd(n*(d - 1) + 1). So a 4-heap with 21 items takes log4(20*(4 - 1)+1), or 2.96 levels. We can’t have a partial level, so we round up to 3.

The primary implementation difference between a binary heap and a d-heap is in the code in the SiftDown method that finds the smallest child. The binary heap has only two nodes to check, so that can be done directly. In a d-heap, you have to write a loop that checks the d child nodes.

The only other big difference is that Heapify has to check fewer nodes when building the heap. Consider, for example, a fully-populated 4-heap:

There are 21 nodes in only three levels. 16 of those nodes are at the leaf level, meaning that they don’t need to be sifted down. You can build a d-heap of n items by checking only (1+(n/d)) nodes.

It should be clear that adding an item to a 4-heap will be faster than adding an item to a 2-heap of the same size. For example, if you wanted to add an item to that 4-heap shown above, BubbleUp would do a maximum of three iterations. A binary heap with 20 nodes requires five levels, meaning that you might have to make up to five iterations.

Nothing’s free, though. Removal becomes more expensive. Although there are fewer levels, each iteration of the loop in the SiftDown method takes a little bit longer as d increases. With a binary heap, you only have to make two node comparisons at each iteration (finding the smallest child takes one comparison, and comparing the node you’re inserting with the smallest child takes the other). A 4-heap has fewer levels to sift down, but each level requires more processing because it has to do four comparisons to find the smallest child.

In a d-heap, each level you sift down requires d node comparisons.

We can’t just increase d and expect better performance. For example, if you were to build a 100-heap (i.e. each node has 100 children), then removing an item from a heap containing 100 items would be like removing from a linear list.

The answer to the question of the optimal value for d is, as you might expect, “it depends.” The math indicates that a 3-heap should be faster than a 2-heap, a 4-heap about the same speed, and a 5-heap slightly slower. My testing shows that the optimum value is usually three or four, and sometimes a 5-heap outperforms those. I’ve yet to find a case where a 2-heap outperforms a 3-heap. I’m going to ask you to trust me on that until we get the thing built and put it through its paces. Then we can compare the theoretical performance against real-world data.

I’ve spent a lot of time on discussion because it’s important to understand these issues completely before building a generic heap class. Now that you have a good understanding, it’s almost time to start coding. Next time I’ll show you the modifications required to make the code flexible so that it can support Max-heap as well as Min-heap. After that we’ll talk about the API that the heap class should present to clients. Then we start coding. You’ll find, though, that we’ve already done the heavy lifting with BubbleUp and SiftDown. Most of the rest is just making the heap behave like other .NET collections.

It’ll be a week or 10 days before I post the next in this series. I’ll be attending the Texas Woodcarvers Guild Fall Extravaganza all next week. Five days of woodcarving classes, followed by a public show and sale on Saturday and Sunday. I’ll have my tablet computer, but nothing on which I can do any programming. And probably no time for programming, anyway.