I introduced the binary heap data structure in my previous post by proposing a more efficient way to manage a collection of cubes. If you recall, I said that any child could learn to maintain a binary heap and that implementing one in code is almost as easy. This time I’ll prove it by creating a rudimentary binary heap class that will store integers. In a later post I’ll show a complete heap implementation that supports generics.
A binary heap is a binary tree with two additional constraints:
- It satisfies the shape property. That is, it’s a complete binary tree. All levels of the tree, except possibly the lowest level, are fully populated. If the last level is not fully filled, the nodes are filled from left to right.
- It satisfies the heap property. Any node in the tree is less than or equal to its children. As a result, the node with the minimum value is always at the root of the tree.
Rule 2 is the rule for what we call a Min-heap. You can also create a Max-heap in which the root is the node with the maximum value, and each node’s value is greater than or equal to its children. The difference in code between a Min-heap and a Max-heap is minimal: you just change the sense of a few comparison operators. I’m going to focus on Min-heap here, with the understanding that everything applies equally to Max-heap. In a later post I’ll show how to use the same code to implement both.
I’m making a change to the way I show the heaps. In the last post I just showed the items arranged in a pyramid. I did that because I didn’t want to confuse the issue with a technical drawing. From now on I’m going to use graphs generated by Graphviz. It’s much easier on me, and more of what you’d expect from an article about algorithms. The last heap shown in my previous post, then, looks like this.
You can see that this tree satisfies both rules. All levels except the last are filled, and the single node on the last level occupies the leftmost position. In addition, every node is smaller than its children. That is, 3 is smaller than 11 and 5. 11 is smaller than 38 and 23, etc.
A sometimes confusing property of heaps is that for any given n greater than 2, there are multiple valid heap arrangements. Here are two other valid arrangements of those same eight items.
Both of those are valid heaps because no node is smaller than its parent, and the lowest level is left-filled. If you were to apply the item removal rules repeatedly to each of those heaps, the items would come out in the proper order: 3, 5, 11, 23, 37, 38, 41, 50. If you don’t believe me, sit down with a piece of paper and give it a whirl.
Because each level of the binary heap contains twice as many nodes as the previous level, it’s very easy to represent a binary heap in an array. Consider this image, in which I’ve labeled the heap nodes from 0 to 14.
Each heap node is labeled with its corresponding index in an array, with the rood node at position 0. The children of node 0 are 1 and 2. The children of 1 are 3 and 4. The children of 5 are 11 and 12. Given a node’s index, x, its child node indexes are (2*x)+1 and (2*x)+2.
Similarly, a node’s parent is at trunc((x-1)/2). So the parent of node 12 is 5, and the parent of node 13 is 6.
The previous heap shown above can be represented in an array as: [3, 23, 5, 37, 41, 11, 50, 38].
Given that, let’s take a look at how we’d implement a binary heap in C# code. Again, the code we’re developing here is designed to create a Min-heap of integers. We’ll extend it later. For now we want to get the basic idea down. Rather than an array, I’ll use a List<T> as a backing store. That gives us array-like functionality with the addition of automatically resizing when we go off the end. The Insert and Remove methods (and eventually all of the heap methods) operate on this list.
private List<int> _items = new List<int>();If you remember the rules from the last post, inserting an item involves placing that item at the end of the heap and bubbling it up through the nodes to its final resting place. Removing the smallest node involves placing the last item in the heap at the newly vacated root position and sifting it down through the heap to its proper position. Those two functions, BubbleUp and SiftDown are the critical operations in the heap.
The code to insert an item is a direct translation of the rules we outlined last time:
- Add the item to the first empty spot in the structure. That is, the lowest, leftmost unoccupied position.
- Bubble up. While the item is smaller than its parent, swap the item with its parent. If the node gets to the top of the tree, stop. The root has no parent.
public void Insert(int newItem)
{
// Add item to the end of the list.
_items.Add(newItem);
// Get index of the newly added item.
int ix = _items.Count - 1;
BubbleUp(ix);
}
private void BubbleUp(int ix)
{
// While item is smaller than its parent, bubble up.
while (ix > 0 && _items[ix] < _items[(ix - 1)/2])
{
// Swap item with its parent.
Swap(ix, (ix - 1)/2);
// Adjust index
ix = (ix - 1)/2;
}
}
private void Swap(int x, int y)
{
int temp = _items[x];
_items[x] = _items[y];
_items[y] = temp;
}Removing an item is similarly simple. Remember the rules:
- Remove the item in the first position. This is the smallest item.
- Move the last item in the structure to the first position.
- Sift down. While the item is larger than the smallest of its children, swap with the smallest child. If the item has no children, stop.
The code is a direct translation:
public int Remove()
{
// Can't remove an item that isn't there.
if (_items.Count == 0)
{
throw new InvalidOperationException("The heap is empty!");
}
// Get the first item.
int smallest = _items[0];
// Copy the last item to the first position.
_items[0] = _items[_items.Count - 1];
// Remove the last item
_items.RemoveAt(_items.Count - 1);
if (_items.Count > 0)
{
SiftDown(0);
}
return smallest;
}
private void SiftDown(int ix)
{
// We can stop when ix is past the halfway point
// because all items beyond this point have no children.
while (ix < _items.Count / 2)
{
// find the smallest child
int ixChild = (ix * 2) + 1;
if (ixChild < _items.Count - 1 && _items[ixChild] > _items[ixChild + 1])
{
ixChild++;
}
// If the item is <= the smallest child, we're done.
if (_items[ix] <= _items[ixChild])
{
break;
}
// Swap the item with the smallest child.
Swap(ix, ixChild);
// And adjust the index.
ix = ixChild;
}
}With the addition of a Count property so that you can tell how many items are in the heap, and a Peek method that lets you examine the smallest item, you have a minimally functional binary heap class. Granted, it only works for integers, but you have to start somewhere.
There is one other function that a heap really should support: quickly initializing a heap from a collection. Typically that’s done with a constructor overload, like this:
public BinaryMinHeap(IEnumerable<int> collection)
{
}The simple-minded way to initialize a heap with a collection is to call Insert for each item in the collection. So, for example, the code inside the constructor above might be:
foreach (int i in collection)
{
Insert(i);
}That will work, but it’s expensive. Every item that added is bubbled up from the bottom. Imagine starting with an empty heap and adding 127 items in reverse order (i.e. 127, 126, 125, 124, etc.). Each new item is smaller than all the other items, so every item will require the maximum number of swaps to bubble up from the last position to the top. Think of it this way. The first item that’s added makes zero swaps. The next two items make one swap each. The next four items make two swaps each. Eight items make three swaps. 16 items make four swaps. 32 items make five swaps, and 64 items make six swaps.It works out to:
0 + 2*1 + 4*2 + 8*3 + 16*4 + 32*5 + 64*6
0 + 2 + 8 + 24 + 64 + 160 + 384 = 642 swapsThere is a better way. It involves first copying the array to the _items list. Then, starting in the middle of the list and working backwards to the head of the list, sift items down.
We can start at the midpoint because in any heap, half of the nodes are leafs: they have no children. If a node has no children then it makes no sense to try sifting it down. So right from the start, 64 of the items make no swaps at all. Remember, we’re working backwards so the next 32 items make one swap each. 16 items make two swaps, eight make three, four make four, two make five, and one makes six. The progression looks like this:
64*0 + 32*1 + 16*2 + 8*3 + 4*4 + 2*5 + 1*6
0 + 32 + 32 + 24 + 16 + 10 + 6 = 120 swapsNote that those are both worst case scenarios. And, yes, the operation works for any arrangement of items.
The resulting heap is not the same as if you had called Insert for every item added, but it’s still a valid heap.
Creating a heap by inserting n items will take time proportional to n*log2(n). Creating a heap by copying all the items into the list and rearranging as described above takes time proportional to n. You can see from the calculations above that the difference is large even with just 128 items. If you’re initializing a heap of one million items, inserting items individually will do on the order of 20 million swaps. Building the heap the other way will do approximately one million swaps; it’s 20 times as fast.
The operation that turns a random list into a heap is typically called Heapify. It’s incredibly simple:
private void Heapify()
{
for (int i = _items.Count/2; i >= 0; --i)
{
SiftDown(i);
}
}The constructor, then, creates a new list from the passed collection and then call Heapify, like this.
public BinaryMinHeap(IEnumerable<int> collection)
{
_items = new List<int>(collection);
Heapify();
}That’s it for now. Next time I’ll show a few examples of how to use the binary heap.