I mentioned before that my discussions have been focused on a Min-heap: a heap in which the root node contains the smallest value, and the value of any node is less than or equal to the values of its child nodes. I also said that to the implementation difference between a Min-heap and a Max-heap (a heap in which the root node contains the largest value, and a node’s value is greater than or equal to the values of its child nodes) amounted to nothing more than changing the sense of a few comparisons. It’s time I show how that’s done, because we’ll be needing it soon.
Consider the BubbleUp
and SiftDown
methods from our BinaryHeapInt
class:
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 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;
}
}
There are three places where we compare items. Unfortunately, one uses <
, one uses >
, and one uses <=
. Before doing anything else, let’s make them all use >
, which will make later changes easier to reason about. So the comparison in BubbleUp
becomes:
_items[(ix - 1) / 2] > _items[ix]
And the second comparison in SiftDown
becomes:
if (!(_items[ix] > _items[ixChild]))
That last one was “less than or equal to,” so I had to change it to “not greater than.”
Now, if we wanted to make a Max-heap all we’d have to do is change those three >
operators to <
.
I dislike duplicating code, though. I’m certainly not going to write separate BubbleUpMin
and BubbleUpMax
methods. I’d much rather change the existing method so that it’s flexible. That’s easy enough to do with a comparison delegate, but first we need to change those lines so that there’s a value to pass to the comparison delegate.
The statement:
if (_items[ix] > _items[ixChild])
is the same as:
if (_items[ix].CompareTo(_items[ixChild]) > 0)
Using CompareTo
here gives me a value that I can pass to a comparison delegate. So if I have a comparison delegate that takes an Integer
parameter (the result of an item comparison) and returns true
if the value is greater than zero, I can write:
if (_resultComparer(_items[ix].CompareTo(_items[ixChild])))
That helps me because I can then define two result comparison methods and a delegate that I can set to say which one I want. For example:
protected static bool MinHeapComparer(int rslt)
{
return rslt > 0;
}
protected static bool MaxHeapComparer(int rslt)
{
return rslt < 0;
}
private readonly Func<int, bool> _resultComparer = MinHeapComparer;
Now I can create a Min-heap or a Max-heap by changing the result comparer. The comparers are protected
because they will be used by inherited classes. I’ll show how that’s done in my next post.
Just for reference, I’ve reproduced the new BubbleUp
and SiftDown
methods at the end of this post. We’ll come back to these methods one more time when we make the changes to support generics and custom comparisons. But this is what we’ll be starting with.
Okay, now we’re ready to define the interface and start coding. Really. See you next time.
private void BubbleUp(int ix)
{
// While item is smaller than its parent, bubble up.
while (ix > 0 && _resultComparer(_items[(ix - 1)/2].CompareTo(_items[ix])))
{
// Swap item with its parent.
Swap(ix, (ix - 1) / 2);
// Adjust index
ix = (ix - 1) / 2;
}
}
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 &&
_resultComparer(_items[ixChild].CompareTo(_items[ixChild + 1])))
{
ixChild++;
}
// If the item is <= the smallest child, we're done.
if (!(_resultComparer(_items[ix].CompareTo(_items[ixChild]))))
{
break;
}
// Swap the item with the smallest child.
Swap(ix, ixChild);
// And adjust the index.
ix = ixChild;
}
}