The IHeap interface

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.

Bandsaw tricks

I picked up a piece of Bethlehem Olive last year before Christmas, with the intention of carving a bird or two from it. I’d already finished the 100 Birds Project, so there was no big rush. Yesterday (yes, about 10 months later) I was making a few birds and thought I’d see what I could do with the olive.

The piece of wood wasn’t quite 2″ thick, so I had to use a smaller bird pattern: 1-1/2 inches wide and 3-3/8 inches long. The piece of wood, though, was slightly less than 6 inches long. How to get two birds out of that piece of wood?

It was easy enough to lay out the two birds so that they fit on the piece of wood:

olive1The problem is making the top cutout. It’s real important to have a flat surface contacting the bandsaw table. Here’s what I need to cut out.

olive2Were I to try cutting this out, I would have to be very careful when working on the tail. The saw would be pushing down on that tail end, and if I let that happen then I’d lose control of the piece. Very bad things can happen then. And whereas it’s fun to say, “don’t do that,” I already know that I’m no match for a 3/4 HP electric motor.

I could turn the block over and glue the top pattern to the curved part, but that distorts it. The tail would be shorter because it would be going down at an angle. I made that mistake early in my time working with a bandsaw.

My solution was to trace the curve on another piece of wood, cut it out on the bandsaw, and use it as the base, like this.

olive3I taped those together and had a good solid flat base. Then I cut the top outline. The result, after removing the base and turning the thing over:

olive4I then turned the piece on its side and cut out the other view.

Doing this made me realize that I don’t have to cut out the entire top view, which saves me having to tape the sides back on before cutting out the side view. I had a few other birds to cut out (this time from full-sized blocks), so I gave it a try.

I cut the top view on one side from beak to tail. Then turn off the saw, leaving me with this:

plum1Note that I’ve lifted the guides so that you can see the work more clearly. When sawing, the guides are adjusted so that they are 1/8 inch to 1/4 inch above the work piece as shown in the next picture.

The reason I stop the saw is because I back the blade out of the cut. I can tell you from experience that backing a blade out of a cut while the saw is running is a dangerous thing to do. It’s one thing to back it out of a short, straight cut. It’s something else entirely to try backing out of a long, curved cut. The blade has a tendency to bind, which will pull it forward out from between the upper and lower guides. Then it catches the work piece and tears it out of my hand.

I was lucky the one time it happened to me; the blade was kinked beyond repair. It could have destroyed the work piece, or the blade could have cut me very badly. It’s never a good idea to lose control of the work piece. Even a small 3/4 horsepower saw like mine can do some serious damage.

That’s one reason for putting the guides close to the work. The less blade exposed, the less damage it can do.

If you want to back out of a cut, turn off the saw. Then hold a small scrap of wood or a pencil against the front of the blade to keep it in place, and gently work the piece back along the cut.

plum2After cutting both sides this way, I turned the piece on its side and cut out the other profile. I had to apply a little pressure when cutting out the beak, because the top side wanted to chatter a bit. But this was easier and faster than cutting the top profiles completely and then taping the sides back on like I used to.

Now I just have to finish those birds . . .

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

The d-ary heap

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:

heap4-1

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:

heap4-2

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:

heap4-3

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.

Hillbilly knife handle

A while back I posted a custom carved knife handle. That one went to the guy who made the knife and sent it to me. I finally sat down and carved the other, which I get to keep.

Nothing fancy here. Just a simple hillbilly. Now to put an edge on it and start carving.

image

On another note, I’m posting this from my Samsung tablet using the WordPress for Android app. Not too bad, although I don’t think I’d want to write a lengthy post with this on-screen keyboard.

Uses for heaps

Back in July I wrote a two part series about turning traditional input, process, output (IPO) applications into producer-consumer applications using multiple threads. The first part explored the issues and the second part presented code that compares different approaches to the problem. I had planned a third part but realized that in order to complete it I needed a priority queue. I could have, and perhaps should have, used a SortedList for my priority queue, but I didn’t. Instead, I put off finishing that series until I could talk about priority queues.

To review, the program has an input thread, a processing thread, and an output thread. The input thread reads a file and places lines on a queue. The processing thread reads individual lines from the input queue, processes them, and places the result on the output queue. The output thread reads lines from the output queue and writes them to a file.

My plan was to add a second processing thread to show how you would speed the program up if the per-line processing took a long time. But if I did that, then lines could go into the output queue in the wrong order and the result would be a scrambled file.

Let me illustrate the problem with integers. The program below starts two processing threads, each of which reads the input queue. The threads simulate processing by sleeping for a short period. One thread takes 500 milliseconds to process an item and the other takes a full second. The output thread reads the output queue and writes to the console.

    private void DoStuff()
    {
        var inputQueue = new BlockingCollection<int>();
        var outputQueue = new BlockingCollection<int>();

        var processQueue = new Action<int>((delay) =>
        {
            foreach (var i in inputQueue.GetConsumingEnumerable())
            {
                Thread.Sleep(delay);
                outputQueue.Add(i);
            }
        });

        var outputData = new Action(() =>
        {
            foreach (var i in outputQueue.GetConsumingEnumerable())
            {
                Console.Write(i + ", ");
            }
            Console.WriteLine();
        });

        // start two processing threads
        var t1 = Task.Factory.StartNew(() => processQueue(500));
        var t2 = Task.Factory.StartNew(() => processQueue(1000));

        // and one output thread
        var t3 = Task.Factory.StartNew(() => outputData());

        // fill the input queue
        var nums = new int[] { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 };
        foreach (var i in nums)
        {
            inputQueue.Add(i);
        }
        inputQueue.CompleteAdding();

        // wait for all processing to be complete
        Task.WaitAll(t1, t2);
        outputQueue.CompleteAdding();

        // and wait for output thread to finish
        t3.Wait();
    }

The program’s output is:

    0, 1, 2, 4, 3, 5, 7, 6, 8, 9,

Items 3 and 6 are out of order!

The way to solve the problem is for the output method to keep track of which item it’s expecting, and not write until that item comes in. To do that, the output method has to save items that come in out of order. That’s where a priority queue comes in. Rather than pulling items from the output queue and outputting them directly, the program puts it on a heap and then outputs items as long as the lowest item on the heap is the expected item. Like this:

    var outputData = new Action(() =>
    {
        var expectedItem = 0;
        var buffer = new BinaryHeapInt();
        foreach (var i in outputQueue.GetConsumingEnumerable())
        {
            buffer.Insert(i);
            // Output any items in the buffer that are in order.
            while (buffer.Count > 0 && buffer.Peek() == expectedItem)
            {
                Console.Write(expectedItem + ", ");
                buffer.Remove();
                ++expectedItem;
            }
        }

        // empty the buffer of all remaining items.
        while (buffer.Count > 0)
        {
            Console.Write(buffer.Remove() + ", ");
        }
        Console.WriteLine();
    });

I realize that the code isn’t optimum. In particular, it’s silly to always add the item to the heap, since in most cases the heap will be empty and the item removed from the queue is probably the expected item. Doing it this way illustrates the point more clearly, and the cost of a heap insertion and removal is so small in comparison to whatever output the code will be doing, that the small inefficiency just wouldn’t matter.

That solution works great as long as items don’t get too far out of order. If most items are processed in a few milliseconds but some items can take several minutes, the heap (buffer in the code above) will have to hold thousands of items. That could be a problem if records are large.

This method also will fail if one of the processing threads drops the ball. The output thread will keep adding items to the buffer, waiting for an item that isn’t coming. But I suppose you have bigger problems than an overflowing output queue if one of your processing threads crashes or goes into an infinite loop on a particular item.

Another solution to the problem would be to make the outputQueue itself a priority queue. That’s possible with BlockingCollection, but it assumes you have a concurrent priority queue class that implements the IProducerConsumerCollection interface. We don’t have such a thing. Yet.

Another use for heaps is selection: picking the best (defined as those with the highest value, however you compute that) items from a large list of candidates. In one memorable case, I had to select the most relevant 200 items from a list of over two million. We computed a relevancy score for each of the items, and then selected those that had the highest score. The naive way to do this is to sort the items by relevancy and then take the last 200 from the resulting array. That’s effective, but expensive. Comparison sorting is an O(n log n) operation. Sorting two million items takes a relatively long time.

With a heap, you can perform the selection in time proportional to n log k, where k is the number of items you want to select. The idea is that you build a heap of the first k items. Then, for each subsequent item in the list, you compare it against the smallest item on the heap (Peek()). If the new item is larger than that smallest item, remove the smallest item and add the new item. It looks like this:

    private List<int> SelectTopK(List<int> items, int k)
    {
        // build a heap from the first 200 items
        var heap = new BinaryHeapInt(items.Take(k));

        // for each successive item . . .
        foreach (var i in items.Skip(k))
        {
            if (i > heap.Peek())
            {
                heap.Remove();
                heap.Insert(i);
            }
        }

        // build a list from the heap contents
        var result = new List<int>();
        while (heap.Count > 0)
        {
            result.Add(heap.Remove());
        }
        return result;
    }

A side effect of using the heap in this way is that the resulting list of top k items is in ascending order.

I discussed that selection algorithm in much detail a while back in When theory meets practice.

A variation on that selection algorithm is selecting the fewest number of items whose sum is at least some value, N. In the above example you might want to have a list of items whose sum is 5,000 or more, but you don’t want more items than you have to take. So if one number is 5,001, then your list will contain a single number.

This, too, is solved with a heap. The idea is to keep track of the sum, and remove things from the heap if doing so won’t take the sum below the target. The code looks like this:

    private List<int> SelectTopSum(List<int> items, int target)
    {
        var heap = new BinaryHeapInt();
        int runningTotal = 0;
        foreach (var i in items)
        {
            if (runningTotal < target)
            {
                // Haven't reached the target yet, so just add it
                runningTotal += i;
                heap.Insert(i);
            }
            else if (i > heap.Peek())
            {
                // Current item is larger than the smallest item on the heap.
                // Remove the small item and add this one.
                runningTotal -= heap.Remove();
                runningTotal += i;
                heap.Insert(i);
            }
            // Remove items from the heap to make runningTotal
            // as small as possible, but still >= target
            while ((runningTotal - heap.Peek()) >= target)
            {
                runningTotal -= heap.Remove();
            }
        }
        // build a list from the heap contents
        var result = new List<int>();
        while (heap.Count > 0)
        {
            result.Add(heap.Remove());
        }
        return result;
    }

Those are just three examples of how I’ve used heaps in production code. There are many more. I find the heap data structure so useful that I’m surprised the .NET Framework’s runtime library doesn’t include one. As you’ll see, it’s not especially difficult to take the rudimentary BinaryMinHeapInt class and turn it into a full blown collection class that supports generics, IEnumerable<T>, and the other things we’ve come to expect from .NET collection classes.

Before we do that, though, I want to introduce a more generalized heap that is as easy to implement as the binary heap but can be a good bit faster in execution. The binary heap works well and is reasonably fast but if I can get a good speed improvement for just a little extra work, I’ll take it.

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.