I tracked down a bug the other day that really surprised me. Again, not because of the code itself, but rather that the person who wrote the code should have known better.

If you want to sort a list of a user-defined type in C# (and other languages), you need a comparison method. There are several different ways to do that, perhaps the simplest being to create a comparison delegate. For example, if you have this class definition:

    public class Foo
    {
        public int Id {get; private set;}
        public string Name {get; set;}
        // constructor and other stuff here . . .
    }

And a list of those:

List<Foo> MyList = GetFooThings(...); Now, imagine you want to sort the list in place by Id. You can write:

    MyList.Sort((x,y) => { return x.Id.CompareTo(y.Id); });

CompareTo will return a value that is:

• Less than 0 if x.Id < y.Id
• Equal to 0 if x.Id = y.Id
• Greater than 0 if x.Id > y.Id

The code I ran into was similar, except the programmer thought he’d “optimize” the function. Rather than incurring the overhead of calling Int32.CompareTo, he took a shortcut:

    MyList.Sort((x,y)) => { return x.Id - y.Id; });

His thinking here is that the result of subtracting the second argument from the first will contain the correct value. And that’s true most of the time. It’s not at all surprising that his testing passed. After all, 12 - 3 returns a positive number, 300 - 123456 returns a negative number, and 99 - 99 returns 0.

But he forgot about negative numbers and integer overflow. Subtracting a negative number is like adding a positive number. That is, 4 - (-1) = 5. And in the artificial world of computers, there are limits to what we can express. The largest 32-bit signed integer we can express is Int32.MaxValue, or 2,147,483,647. If you add 1 to that number, the result is Int.MinValue, or -2,147,483,648. So the result returned by the comparison delegate above, when x is a very large number and y is a sufficiently small negative number is incorrect. It will report, for example, that 2,147,483,647 is smaller than -1!

There’s a reason that Int32.CompareTo is written the way it is. Here it is, directly from Microsoft’s Reference Source:

    public int CompareTo(int value) {
        // Need to use compare because subtraction will wrap
        // to positive for very large neg numbers, etc.
        if (m_value < value) return -1;
        if (m_value > value) return 1;
        return 0;
    }

It seems like I run into these fundamental errors more often now than I did in the past. I’m not yet sure of the reason. I’ve been active in the online programming community for 30 years, and have seen a lot of code written by programmers of all skill levels. Early on, the average skill level of the programmers I met online was much higher than it is today. These days, every Java programming student has access to Stack Overflow, and I see a lot of these rookie mistakes. But I also see many such mistakes made by more experienced programmers.

I’m wondering if the difference is one of education. When I started programming, we learned assembly language early on and actually used it to write real programs. Two’s complement integer representation was a lesson we learned early, and integer overflow was something we dealt with on a daily basis. We would not have made this mistake. No, we made much more interesting mistakes.

This error can be caught, by the way. If you enable runtime overflow checking in C#, the runtime will throw an exception if the result of an arithmetic operation results in overflow or underflow. But that check is almost always turned off because it can have a large negative impact on performance, and in many places we depend on integer overflow for our algorithms to work correctly. It’s possible to disable overflow checking for a specific expression or block of code, but in my experience that functionality is rarely used. You can also disable the check globally but enable it for specific expressions or blocks of code, but doing so requires that you understand the issue. And if a programmer understood the issue, he wouldn’t have written the erroneous code in the first place.

Errors like this can exist in a working program for years, and then crop up at the most inopportune time when somebody uses the code in a new way or presents data that the original programmer didn’t envision. As much as our languages and tools have evolved over the past 30 years, in some ways we’re still distressingly close to the metal.

Up to this point, I’ve been showing paring heap nodes as having a child list. Conceptually, the node structure looks like this:

    class HeapNode
        public int Data;
        public HeapNode[] Children;
    }

That’s a good conceptual model, but implementing that model can be unwieldy, and can consume a huge amount of memory. When working with small objects in managed languages like .NET, memory allocation overhead can easily exceed the memory used for data. That’s especially true of arrays, which have a 56-byte allocation overhead.

Granted, not all nodes in a pairing heap have children. In fact, at most half of them will. So we can save memory by not allocating an array for the children if there aren’t any. But that adds some complexity to the code, and at best saves only half of the allocation overhead.

Using the .NET List<T> collection doesn’t help, because List<T> uses an array as the backing store. LinkedList<T> will work, but involves its own overhead what with having to manage LinkedListNode instances.

In short, managing a per-node list of children can be difficult.

In my introduction to the Pairing heap, I showed this figure:

    2
    |
    8, 7, 3
    |     |
    9     4, 5
          |
          6

2 is the root of the tree. It has child nodes 8, 7, and 3. 9 is a child of 8. 4 and 5 are children of node 3, and 6 is a child of 4.

More traditionally, that tree would be drawn as:

                   2
                 / | \
                8  7  3
               /     / \
              9     4   5
                   /
                  6

That’s the traditional view of the tree. But we can also say that 8 is the first child of 2, 7 is the sibling of 8, and 3 is the sibling of 7. That is, every node has a reference to its first child, and to its next sibling. The node structure, then, is:

    class HeapNode
        public int Data;
        public HeapNode FirstChild;
        public HeapNode Sibling;
    }

As it turns out, there’s a well known binary tree structure called Left-child-right-sibling. Any traditional tree structure can be represented as such a binary tree. Our tree above, when represented as a left-child-right-sibling binary tree, becomes:

                 2
                /
               8
              / \
             9   7
                  \
                   3
                  /
                 4
                / \
               6   5

You might notice that this structure bears striking similarity to the original figure from my introduction. It’s the same thing, only rotated 45 degrees clockwise.

As you can see, this builds a very unbalanced binary tree. That’s okay, since we’re not searching it. With pairing heap, all of the action is at the first few levels of the tree. A deep tree is good, because it means that we rarely have many siblings to examine when deleting the smallest node.

Implementing a Pairing heap in a left-child-right-sibling binary tree is incredibly easy. Next time I’ll show a simple implementation in C#.

It’s surprising how many Computer Science articles and textbooks, when showing how to implement a binary heap in an array, present code that has the root node at index 1 in C-like languages where the first element of an array is at index 0. In those implementations, element 0 in the array is unused.

This bothers me. Not because the code wastes an insignificant amount of memory, but because it leads to a lot of confusion among students and junior programmers who are trying to implement a binary heap. Off-by-one errors abound, the first being in allocating the heap array. Here’s a common error that occurs when allocating a heap to hold 100 integers.

    int[] heap = new int[100];

We’re conditioned from the very start of our programming education to begin counting at 0. Every time we have stuff in an array or list, the first thing is at index 0. Every array-based algorithm we work with reinforces this lesson. We’re taught that some languages used to start at 1, but those heretical languages have nearly been eliminated from the world. And then they foist this folly on us: a heap’s root is at index 1.

We’re taught that 100 items means indexes 0 through 99. It’s beaten into our heads on a daily basis when we’re learning programming. Then they trot out this one exception, where we have to allocate an extra item and count from 1 to 100 rather than 0 to 99 like normal programmers do.

Some people say, “but if you start at 0, then the calculations to find the children won’t work.” Well, they’re partially right. If the root is at index 1, then the left child of the node at index x is at index (x * 2), and the right child is at index (x * 2) + 1. The parent of the node at index x is at index x/2. They’re right in that those calculations don’t work if you move the root to index 0. But the changes required to make the calculations work are trivial.

If the root is at index 0, then the left child is at (2 * x) + 1, right child at (2 * x) + 2, and parent at (x-1)/2.

The hard core optimizer will tell you that the extra addition in computing the left child, and the extra subtraction when computing the parent will incur a big performance hit. In truth, in the context of a real, working computer program, the performance difference is down in the noise. It’s highly unlikely that your program’s overall performance will suffer from the addition of a couple of ADD or SUB instructions in a binary heap implementation. If it does, then you’re doing something horribly wrong. Doing something stupid in order to save a few nanoseconds here and there is … well … stupid.

No, I think the real reason we continue this madness is historical. The first known reference to a binary heap is in J.W.J. Williams’ implementation of Heapsort (Williams, J.W.J. (1964), ‘Algorithm 232: Heapsort’, Communications of the ACM 7 (6), 347-348). Yes, that’s right: 52 years ago. His code sample, like all ACM code samples at the time, was written in Algol, a language in which array indexes start at 1.

Textbooks with code samples in Algol and, later, Pascal, perpetuated the idea that the root of a binary heap must be at index 1. It made sense, what with 1 being the first index in the array. When those books were revised in the 1990s and the examples presented in C, Java, C++, etc., a literal conversion of the code maintained the 1-based root even though arrays in those languages are 0-based. Nobody stopped to consider how confusing that empty first element can be to the uninitiated.

What I find disturbing is that whoever did the code conversions almost certainly ran into an off by one problem when testing the examples. But rather than spend time to rewrite the code, they “fixed” the problem by allocating an extra item, and maybe explained it away in the text as something that just has to be done to keep the root at index 1. Those few who actually understood the issue seem to have been too lazy to make the correction, opting instead to explain it away as a performance issue.

In so doing, they’ve done their audiences a grave disservice. I find that inexcusable.

I ran across a problem today that I think would make an excellent interview question.

You work in a warehouse that has N storage compartments, labeled D-1 through D-N. Each storage compartment can hold one shipping crate. There’s also a temporary holding area, called D-T, that can hold a single crate. There also are N crates, labeled C-1 through C-N, each of which is in a storage compartment.

There is a forklift that can pick up a single crate, move it to an empty position, and put it down.

The owner, after touring the facility, decreed that the crates must be rearranged so that crate C-x is in space D-x (C-1 in D-1, C-2 in D-2, … C-N in D-N).

What algorithm would you employ to rearrange the crates in the minimum number of moves?

This is a fairly simple problem. If you pose it as a “balls and bins” problem, with a physical model to play with, most people will develop the optimum algorithm in a matter of minutes. But pose it as a programming problem and a lot of programmers have trouble coming up with the same algorithm.

If you’re interested in trying the problem yourself, cut five squares (crates) from a piece of paper, and label them C1 through C5. Draw six boxes on another sheet of paper, and label them D1 through D6. Now, arrange the crates on the spaces in this order: C4, C1, C5, C3, C2. Leave D6 empty. Finally, rearrange them. Remember, if you pick up a card you have to place it in an empty spot before you can pick up another card.

So if this problem is so simple, why is it such an interesting interview question and why do programmers have trouble with it?

One reason is that it’s not really a sorting problem. At least not in the traditional sense. You see, I’m not asking the candidate to write a sort. In fact, I’m not asking him to write a program at all. I’m asking him to develop an algorithm that will rearrange the crates in a specific order, given the constraints. The candidate’s first reaction tells me a lot about how he approaches a problem. Granted, I have to take into account that the candidate will expect a whiteboard programming problem, but if his immediate reaction is to stand up and start writing some kind of sort method, I can pretty much guarantee that he’s going down the wrong track.

The algorithm that uses the fewest moves is not one that you would typically write. It’s either computationally expensive, or it uses additional extra memory. And there’s a well known efficient solution to sorting sequential items. That algorithm works well in the computer, but is less than optimum when translated to the physical world where it takes time for a forklift to pick up and move an item.

The well known algorithm starts at the first storage compartment, D-1. If the item in that position is not crate C-1, it swaps the crate with the crate in the position that it needs to be in. It continues making swaps until C-1 is in D-1, and then moves on to compartment D-2 and does the same thing. So, for example, if you have five crates that are arranged in the order [4,1,5,3,2,x] (the x is for the empty spot, initially D-T) the sequence of swaps is:

    Swap 4 with 3 (the item that's in position D-4), giving [3,1,5,4,2,x]
    Swap 3 with 5, giving [5,1,3,4,2,x]
    Swap 5 with 2, giving [2,1,3,4,5,x]
    Swap 2 with 1, giving [1,2,3,4,5,x]

At which point the programmer says, “Done!”

The programmer who develops this solution and calls it done might think again if he re-reads the problem statement. Note that nowhere did the algorithm use the temporary location, D-T. Either the programmer will smell a rat, or he’ll dismiss that temporary location as a red herring.

As it turns out, it’s not a red herring. A swap is actually a sequence of three separate operations. Swapping the contents of D-1 and D-4, for example, results in:

1. Move the contents of D-1 to a temporary location.
2. Move the contents of D-4 to D-1.
3. Move the contents of the temporary location to D-1.

The well known solution to the problem–the solution that is in many ways optimum on the computer–results in 12 individual moves:

1. Move crate C-4 from D-1 to D-T.
2. Move crate C-3 from D-4 to D-1.
3. Move crate C-4 from D-T to D-4. (Crate C-4 is in position.)
4. Move crate C-3 from D-1 to D-T.
5. Move crate C-5 from D-3 to D-1.
6. Move crate C-3 from D-T to D-3. (Crate C-3 is in position.)
7. Move crate C-5 from D-1 to D-T.
8. Move crate C-2 from D-5 to D-1.
9. Move crate C-5 from D-T to D-5. (Crate C-5 is in position.)
10. Move crate C-2 from D-1 to D-T.
11. Move crate C-1 from D-2 to D-1. (Crate C-1 is in position.)
12. Move crate C-2 from D-T to D-2. (Crate C-2 is in position.)

In the worst case, of which this is an example, the algorithm makes N-1 swaps, or 3N-3 moves.

At this point, it might be useful to have a discussion about what problem we’re really trying to solve. The problem asked for the minimum number of moves. A reminder that we’re talking about a physical process might be in order. To programmers who are used to things happening almost instantly, a few extra moves here and there don’t really make a difference. The solution presented above is asymptotically optimum in that the number of moves required is linearly proportional to the number of crates. That’s typically a good enough answer for a programming question. But, again, this isn’t really a programming question. One can assume that the client wants to make the minimum number of moves because he has to pay a forklift operator $15 per hour and it takes an average of five minutes for every move. So if he can reduce the number of moves from 12 to 6, he saves $30.

The solution that most people presented with the balls and bins problem develop does things a bit differently. Rather than starting by moving crate C-4 to its rightful place, the algorithm starts by emptying the first bin (i.e. moving C-4 to D-T), and then filling the empty location with the item that belongs there. Then, it fills the new empty slot with the element that belongs there, etc. Let’s see how it works, again starting with [4,1,5,3,2,x].

1. Move crate C-4 from D-1 to D-T.
2. Move crate C-1 from D-2 to D-1. (Crate C-1 is in position.)
3. Move crate C-2 from D-5 to D-2. (Crate C-2 is in position.)
4. Move crate C-5 from D-3 to D-5. (Crate C-5 is in position.)
5. Move crate C-3 from D-4 to D-3. (Crate C-3 is in position.)
6. Move crate C-4 from D-T to D-4. (crate C-4 is in position.)

That took six moves, or half of what the “optimum” solution took. That’s not quite a fair comparison, though, because that’s not the worst case for this algorithm. The worst case occurs when moves result in a cycle that leaves D-T empty before all of the items are in order. Consider the sequence [2,1,5,3,4,x]. Using our new algorithm, we start with:

1. Move crate C-2 from D-1 to D-T.
2. Move crate C-1 from D-2 to D-1. (Crate C-1 is in position.)
3. Move crate C-2 from D-T to D-2. (Crate C-2 is in position.)
   At this point, our temporary spot is empty, so we need to make a new empty spot by moving the first out of place crate to D-T.
4. Move crate C-5 from D-3 to D-T.
5. Move crate C-3 from D-4 to D-3. (Crate C-3 is in position.)
6. Move crate C-4 from D-5 to D-4. (Crate C-4 is in position.)
7. Move crate C-5 from D-T to D-5. (Crate C-5 is in position.)

It’s interesting to note that the swapping algorithm requires three swaps (nine moves) to rearrange items given this initial arrangement.

As far as I’ve been able to determine, the worst case for this algorithm requires 3N/2 moves. It will never make more moves than the swapping algorithm, and often makes fewer.

The point of posing the problem to the candidate is to get him to develop an approach to the problem before he starts coding.

Another interesting thing about this question is that it allows for a follow-on question. Assuming that the candidate develops the optimum algorithm, ask him to write code that, given the starting position, outputs the moves required to rearrange the crates. In other words, implement the algorithm in code.

At this point, he’ll have to make a decision: use sequential search to locate specific crates, or create an index of some kind to hold the original layout so he can quickly look up an individual crate’s location. Again, he should be asking questions because the requirements are deliberately ambiguous. In particular, he might think that he can’t use the index because we only allowed him one extra swapping space for the crates. But again, the original problem statement doesn’t mention a computer program, and the follow-on question doesn’t place any restrictions on the memory consumption.

I’ll leave implementation of the algorithm as an exercise for those who are interested. It’s not difficult, just a bit odd for those who are used to writing traditional sorting algorithms.

Ultimately, the reason I find this problem a potentially useful interview question is because it forces the candidate to differentiate between the customer’s requirements (the optimum sequence of steps required to arrange his crates), and then internal implementation details. The extent to which the candidate can make that differentiation tells me a lot about how she will approach the real-world problems that we’ll present to her on a daily basis. In addition, the simple problem is rife with opportunities to have other discussions about approaches to problems and common coding tradeoffs.

It occurred to me as I was writing this that I should construct a balls and bins prop that I can trot out if the candidate doesn’t trip to the algorithm relatively quickly. It would be interesting to see how quickly the candidate, if given the prop, would discover the optimum algorithm.

I’m kind of excited about getting an opportunity to try this out.

Last time, I introduced the Pairing heap, and showed an example of its structure and how it changes as items are added and removed. At first glance it seems unlikely that this can be faster than the binary heap I spent so much time exploring three years ago. But it can be. Let me show you how.

As I mentioned in the discussion of the binary heap, inserting an item takes time proportional to the base-2 logarithm of the heap size. If there are 100 items in the heap, inserting a new item will take, worst case, O(log₂(100)) operations. Or, about 7 swaps. It could be fewer, but it won’t be more. In addition, removing the minimum item in a min-heap will require O(log₂(n)) operations. In a binary heap, insertion and removal are O(log n).

As you saw in my introduction to the Pairing heap, inserting an item is an O(1) operation. It never involves more than a comparison and adding an item to a list. Regardless of how many items are already in the heap, adding a new item will take the same amount of time.

Removal, though, is a different story altogether. Removing the smallest item from a Pairing heap can take a very long time, or almost no time at all.

Consider the Pairing heap from the previous example, after we’ve inserted all 10 items:

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

It should be obvious that removing the smallest item (0) and re-adjusting the heap will take O(n) operations. After all, we have to look at every item during the pair-and-combine pass, before ending up with:

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

But we only look at n/2 items the next time we remove the smallest item. That is, we only have to look at 2, 8, 3, and 4 during the pair-and-combine pass. The number of items we look at during successive removals is cut in half with each removal, until we get to two or three items per removal. Things fluctuate a bit, and it’s interesting to write code that displays the heap’s structure after every removal.

By analyzing the mix of operations required in a very large number of different scenarios, researchers have determined that the amortized complexity of removal in a Pairing heap is O(log n). So, asymptotically, removal from a Pairing heap is the same complexity as removal from a binary heap.

It’s rather difficult to get a thorough analysis of the Pairing heap’s performance characteristics, and such a thing is way beyond the scope of this article. If you’re interested, I suggest you start with Towards a Final Analysis of Pairing Heaps.

All other things being equal, Pairing heap should be faster than binary heap, simply because Pairing heap is O(1) on insert, and binary heap is O(log n) on insert. Both are O(log n) on removal. Keep in mind, though, that an asymptotically faster algorithm isn’t always faster in the real world. I made that point some time back in my post, When theory meets practice. On average, Pairing heap does fewer operations than does binary heap when inserting an item, but Pairing heap’s individual operations are somewhat more complex than those performed by binary heap.

You also have to take into account that Pairing heap can do some things that binary heap can’t do, or can’t do well. For example, the merge (or meld) function in Pairing heap is an O(1) operation. It’s simply a matter of inserting the root node of one heap into another. For example, consider these two pairing heaps:

    1                  0
    |                  |
    2, 8               5
    |
    4

To merge the two heaps, we treat the root nodes just as we would two siblings after removing the smallest item. We pair them to create:

    0
    |
    1, 5
    |
    2, 8
    |
    4

With binary heap, we’d have to allocate a new array that’s the size of both heaps combined, copy all items from both heaps to it, and then call the Heapify method to rebuild the heap. That takes time proportional to the combined size of both heaps.

And, as I mentioned previously, although changing the priority of an item in a binary heap isn’t expensive (it’s an O(log n) operation), finding the node to change is an O(n) operation. With Pairing heap, it’s possible to maintain a node reference, and it’s been shown (see the article linked above) that changing the priority of a node in a Pairing heap is O(log log n).

Another difference between Pairing heap and binary heap is the way they consume memory. A binary heap is typically implemented in a single contiguous array. So if you want a heap with two billion integers in it, you have to allocate a single array that’s 8 gigabytes in size. In a Pairing heap, each node is an individual allocation, and each node contains two pointers (object references). A Pairing heap of n nodes will occupy more total memory than a binary heap of the same size, but the memory doesn’t have to be contiguous. As a result, you might be able to create a larger pairing heap than you can a binary heap. In .NET, for example, you can’t create an array that has more than 2^31 (two billion and change) entries. A Pairing heap’s size, however, is limited only by the available memory.

A key takeaway from my early discussion of heaps is that if all we need is the ability to get the smallest item whenever we reach into the bag, then there’s no need to keep the entire bag in sorted order if some less expensive alternate ordering will work. Because of that relaxed requirement, we can implement a priority queue with a heap a whole lot more efficiently than with a sorted list.

I like to call it creative laziness.

Binary heaps are useful and quite efficient for many applications. For a pure priority queue, it’s hard to beat the combination of simplicity and efficiency of a binary heap. It’s easy to understand, easy to implement, and performs quite well in most situations. But the simplicity of the binary heap makes it somewhat inflexible, and also can prove to be inefficient when heaps become very large.

Even though the binary heap isn’t sorted, its ordering rules are pretty strict. If you recall, a valid binary heap must satisfy two properties:

• The heap property: the key stored in a node is greater than or equal to the key stored in the parent node.
• The shape property: it’s a complete binary tree.

Maintaining the shape property is required if you want to efficiently implement the binary heap in a list or array, because it lets you implicitly determine the locations of the child or parent nodes. But nothing says that you have to implement a binary heap in an array. You could use a more traditional tree representation, with explicit nodes that have right, left, and parent node references. That has some real benefits.

For example, a common extension to the priority queue is the ability to change the priority of an item in the queue. It’s possible to do that with a binary heap, and in fact isn’t difficult. It’s inefficient, though, because in a binary heap it takes a sequential search to find the item before you can change its priority.

But if you have a traditional tree representation, then you can maintain direct references to the nodes in the heap. At that point, there’s no longer a need for the sequential search to find the node, and changing an item’s priority becomes a pure O(log n) operation. Algorithms such as the A* search algorithm typically use something other than a binary heap for their priority queues, specifically because changing an item’s priority is a common operation.

Another common heap operation is merging (also known as melding): combining two heaps into one. If you have two binary heaps, merging them takes time proportional to the combined size of both heaps. That is, it takes O(n + m) time. The basic idea is to allocate an array that’s the size of both heaps, put all the items into it, and then call a BuildHeap function to construct the heap. With a different heap representation, you can do the merge in constant time.

It turns out that maintaining the shape property when you go to a more traditional tree representation is needlessly expensive. If you eliminate the need for the shape property, it becomes possible to indulge in even more creative laziness.

And, my oh my, have people been creative. Here’s a partial list of heap implementations.

There’s a lot of discussion about which of those is the “fastest” or “best” heap implementation. A lot of it involves theoretically optimum asymptotic behavior, and can get pretty confusing for those of us who just want a working heap data structure that performs well in our applications. Without going into too much detail, I’ll just say that some of those heap implementations that have theoretically optimum performance in some areas (the Brodal queue, for example) are difficult to implement and not at all efficient in real-world situations.

Of those that I’ve worked with, I particularly like Pairing heap because of its simplicity.

The pairing heap’s shape is much different than that of a binary heap. Rather than having right and left child references, a pairing heap node maintains child lists. It maintains the heap property in that any child in a min-heap is greater than or equal to its parent, but the concept of shape is thrown out the window. For example, consider this binary heap of the numbers from 0 to 9.

                    0
              1           3
          5       2   7       4
        9   6   8

Again, in the binary heap, each node has up to two children, and the children are larger than the parents. Although there are multiple valid arrangements of values possible for a binary heap, they all maintain that shape property.

A Pairing heap’s structure is much more flexible. The smallest node is always the root, and children are always larger than their parents, but that’s where the similarity ends. The best way to describe the structure is to go through an exercise of adding and removing items.

If you start with an empty heap and add an item, then that item becomes the root. So, let’s add 6 as the first item in the heap:

    6

Now, we add the value 3. The rules for adding are:

1. If there is no root, then the new item becomes the root.
2. If the new item is greater than or equal to the root, then the new item is added to the root item’s child list.
3. If the new item is smaller than the root, then the new item becomes the root, the old root’s child list is appended to the new root’s child list, and the old root is appended to that child list.

In this case, 3 is smaller than 6, so 3 becomes the root and 6 is added as a child of 3.

    3
    |
    6

Here, the vertical bar character (|) is used to denote a parent-child relationship. So node 6 is a child of node 3.

Now we add 4 to the heap. Since 4 is larger than 3, 4 is added to the child list.

    3
    |
    6,4

When we add 2 to the heap, 2 becomes the new root, and 3 is appended to the child list:

    2
    |
    6,4,3

I’ll add 5, 8, 9, and 7 in that order, giving:

    2
    |
    6,4,3,5,8,9,7

Adding 0 makes 0 the root, and then adding 1 appends to the child list:

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

Note that the heap property is maintained. The smallest item is at the root, and child items and their siblings are larger than their parents. Because the smallest item is at the root, we can still execute the get-minimum function in constant time.

And in fact, insert is also a constant time operation. Inserting an item consists of a single comparison, and appending an item to a list.

Things get interesting when we want to remove the smallest item. Removing the smallest item is no trouble at all, of course. It’s figuring out the new root that gets interesting. This proceeds in two steps:

First, process the children in pairs from left to right, creating 2-node heaps with the lowest item at the root, and the other item as a child. So using the child list above, we would create:

    4 3 8 2 1
    | | | |
    6 5 9 7

So 6 is a child of 4, 5 is a child of 3, etc. In this case, 1 doesn’t have a child.

Then, we process from right to left, taking the lower item as the root and adding the other item as a child of the root. Starting with 1 and 2, we combine them to create:

    4 3 8 1
    | | | |
    6 5 9 2
          |
          7

Proceeding to compare 1 and 8:

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

Note here that 2 and 8 are siblings, but 7 is a child of 2, and 9 is a child of 8. 9 and 7 are not siblings.

When we’re done processing, we have:

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

Again, the heap property is maintained.

It’s very important to understand that the heap property is maintained. All child nodes are larger than their parent nodes. Siblings (children of the same node) are represented in an unordered list, which is just fine as long as each sibling is larger than the parent node. Also, a node’s children only have to be larger than their parent node. Being smaller than a parent’s sibling does not violate the heap property. In the figure above, for example, 5 is larger than its parent, 3, but smaller than its parent’s sibling, 8.

Removing 1 from the heap leaves us with

    2, 8, 3, 4
    |  |  |  |
    7  9  5  6

Again, we pair from left to right. 2 is smaller than 8, so 2 becomes the root of the subtree. But what happens to the children? They’re appended to the child list of the other node. So pairing 2 and 8 results in:

    2
    |
    8, 7
    |
    9

And pairing the others gives:

    2      3
    |      |
    8, 7   4, 5
    |      |
    9      6

And combining from right to left makes 2 the root of the new tree:

    2
    |
    8, 7, 3
    |     |
    9     4, 5
          |
          6

Again, you can see that the heap property is maintained.

Now, when we remove 2 from the heap, we first pair 8 and 7 to create:

    7     3
    |     |
    8     4, 5
    |     |
    9     6

And then combine to form:

    3
    |
    4, 5, 7
    |     |
    6     8
          |
          9

When 3 was selected as the smallest item, node 7 was appended to the child list.

That’s the basics of the Pairing heap. You might be asking yourself how that can possibly be faster than a binary heap. That will be the topic for next time.

Today I got a bug report saying that an error occurred while trying to save a record. That there was an error in this code I inherited isn’t unusual. It was odd, though, to encounter an error in saving a record. That particular bit of code executes hundreds of times per day and I’d never seen a bug report. A few minutes looking at the logs led me to this snippet:

    var outlets = outletRepository.GetOutlets();
    var outletName = outlets.First(outlet => outlet.Id == myRecord.OutletId).Name;

For those of you who don’t speak C#, all that’s doing is getting the list of Outlet records from the database and locating the one that’s referenced by myRecord. We do it this way rather than just looking up the single outlet because we use the returned list of outlets later in the method.

At first I couldn’t figure out why that failed. After all, our database has referential integrity, so myRecord can’t possibly (as far as I know) reference an outlet that doesn’t exist.

It turns out that GetOutlets is defined as:

    public List<Outlet> GetOutlets(bool activeOnly = true)

So a call to GetOutlets() by default returns just the active outlets. Because the outlet referenced by this particular record was marked as inactive, that outlet was not returned by GetOutlets, and as a result the call to Enumerable.First threw an exception.

The most glaring error here is the use of First, which I contend should be used only if you know that what you’re looking for is somewhere in the list. Otherwise you probably should call FirstOrDefault and then check for a null return value.

A more insidious error is the design of the GetOutlets method. In the first place, using a Boolean value to determine whether the method returns all outlets or just the active outlets is a bad idea. true or false are rather ambiguous here. You can’t tell by looking at the value passed what attribute is being tested, or if the flag is used for something else entirely. Maybe true means “sort the records.” Programmers are somehow supposed to “know” what it means. In any case, if the parameter is required the programmer knows that he has to pass true or false in order for it to work. And one would assume that an unfamiliar programmer would check the parameter name and pass the appropriate value. But when you give the parameter a default value, you’ve effectively removed any roadblock to using the method incorrectly. Certainly the statement outlets = outletRepository.GetOutlets(); doesn’t convey any information about the parameter–or that it even exists.

Don’t use Boolean values like this. If you want two forms of the GetOutlets method, then write them.

    public List<outlet> GetAllOutlets();
    public List<outlet> GetOnlyActiveOutlets();

Another option, less preferred but possibly acceptable, would be to define an enumeration that explicitly states what you’re looking for:

    enum OutletFilterType
    {
        All,
        OnlyActive
    }

    public List <outlet> GetOutlets(OutletFilterType filter);

And to call it:

    outlets = GetOutlets(OutletFilterType.All);
    outlets = GetOutlets(OutletFilterType.OnlyActive);

But do not give that parameter a default value.

If you really must take shortcuts in your private implementation–a practice I strongly discourage, by the way, because private code has a distressing tendency to become public–then fine. Make a mess in your own house if you wish, but keep your public interfaces clean and unambiguous.

Every time I think I’m getting a handle on this code, I uncover another little code bomb. The code is littered with this GetXXX(true/false) pattern, and the use of First to get things from untrusted lists. I suppose you could call it job security, but I’m getting tired of it.

Many programmers who write code to work with databases like the concept of an “upsert” command: passing a record to the database and letting it figure out whether the record should be added or updated. If the record already exists in the database then it’s updated. Otherwise a new record is created. It’s very convenient.

It’s also a terrible idea. At least, that’s my experience. Many years ago I argued strongly for an “upsert” command, and on one project I created my data access layer with such a thing. We weren’t using stored procedures on that project, so the “check and update if there” logic was written in code. It worked. It also caused no end of problems, and I swore that I’d never use the upchuck (err … upsert) model again. And I didn’t, until I inherited this project.

The project I’m working on uses the upsert model throughout. The undocumented but well-understood convention is that none of our database tables have a record id of 0. So if I pass a record with id 0 to an upsert stored procedure, the record won’t be found in the table and a new record is inserted. This is convenient for the guy who writes the database access code because he only has to write one method to handle both insert and update. When you’re writing CRUD code for tables that have dozens of fields, that seems like a real savings: you write a whole lot less code.

But it comes at a cost that many don’t recognize: clients who call the upsert method have to know that record id 0 has a special meaning. That’s fine for the original development team, but it’s not at all obvious to a programmer who comes on to the project some time after the program is in production.

It gets worse. In our project we have a Categories table that contains category names and other information. Each Reward that we create belongs to exactly one category, the identifier of which is stored in the Rewards record. There are UI screens that allow system administrators to add new categories. The project is pretty mature now, so we don’t often add new categories.

Unfortunately, whoever wrote those UI screens wasn’t too hip to things. To create the drop-down list of categories, one would typically get all of the categories from the database and create a combo box (drop down) that lets the user select a category from the list. Sometimes the dropdown will have an initial value something like “Select a category,” with a default value. Usually, that label is added in code after getting the list of categories from the database. But not in this case. No, the genius who designed these screens decided that he’d create a category with an id of 0, and text “Select a category.” And he decided that his “no record” id would be -1.

So for Categories and a few other configuration tables, you pass -1 for the record id if you want to insert a new record. Passing 0 just overwrites the existing “Select a category” record.

So now the rule is “Passing a record id of 0 inserts a new record. Except for tables Foo, Bar, and Idiot, for which you must pass a record id of -1.” (Actually, any negative number will do, but I digress.)

Yeah. That’s like totally obvious. Not!

So when we did some refactoring in that area, one of my guys, relatively new to the project, made the reasonable assumption that 0 meant “new record” for this table just like it does for every other table. Imagine our surprise when QA told us that adding a new category just overwrote the record with ID 0.

I’ll grant that the programmer who introduced this bug is at fault for not noticing the difference. I put more blame the programmer who thought it’d be a good idea to special case these few tables for making the mistake not only possible but almost guaranteed to happen. But ultimately the blame goes to whoever decided that the Upsert model was a good idea. If we had separate Insert and Update methods and stored procedures, then there would be no question what was happening. With a separate Insert method, you’d never pass a record id, which would make it impossible to inadvertently do an Update when you meant to do an Insert.

One argument programmers make for the use of Upsert is that, with it, the create new record and edit existing record functions can be identical: initialize the record (either by reading an existing one from the database, or creating a new one with default values), and call the Edit method. When editing is done, just call Upsert and things “just work.” I’ve written code like that. I’ve also been bitten by it because that common Edit method always ends up needing a flag to indicate whether you’re creating new or editing existing, and the method is peppered with if (IsEdit) conditionals. In the end, the “common” Edit method is hugely complex and very fragile. It’s been my experience that the temptation to combine create and edit functionality is very strong, but giving in to it is the first step on a long and painful road.

Upsert is evil. It might be useful on the database end, but it has no use in a data access layer or anywhere else a mere mortal programmer might be. The programmer should know whether his code is editing an existing record or creating a new record, and his code should call the Update or Insert method, as appropriate.