Heaps: cleaning up some code

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;
        }
    }

1 comment to Heaps: cleaning up some code

Categories

A sample text widget

Etiam pulvinar consectetur dolor sed malesuada. Ut convallis euismod dolor nec pretium. Nunc ut tristique massa.

Nam sodales mi vitae dolor ullamcorper et vulputate enim accumsan. Morbi orci magna, tincidunt vitae molestie nec, molestie at mi. Nulla nulla lorem, suscipit in posuere in, interdum non magna.