Heaps: Why is the 0th element in the heap array always null?

In the lesson on Heaps, the Javascript implementation of a heap uses an array with the 0th element always being null and I don’t understand why.

The only reason I can think of is that it makes the calculation of the child indices slightly cleaner (left is 2n and right is 2n+1, as opposed to left is 2n+1 and right is 2n+2 if you have a parent as the 0th element). But to me it feels like a clunky implementation to have an unusable null 0th element, especially when we end up outsourcing the parent/child index calculations to helper functions anyway.

Is there another reason why it’s important to implement a heap as an array with a null 0th element?

I always thought 0-indexed for heaps is more common nowadays. I know CLRS uses 1-indexing but they do that for everything in the book. Perhaps there is some small bump in performance by being able to do operations with bit-shifitng… but not enough of a bump to change the indexing.

Someone can correct me on this if I’m wrong.

1 Like