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.