In the implementation of a binary heap using an array, it's a common practice to leave the index 0 unused. This might seem counterintuitive at first glance, as programming typically emphasizes efficient use of memory. However, there are technical reasons for this decision, which can simplify the algorithms associated with heaps.

Heap Basics

A binary heap is a complete binary tree that satisfies the heap property, which can be a max-heap or a min-heap. In a max-heap, for every node $i$, the value stored at $i$ is greater than or equal to the values in its children. In a min-heap, the value is less than or equal to its children.

The beauty of heaps lies in their efficient array representation. For a node at index $i$, its children and parent can be easily found using simple arithmetic:

• Left Child: $2i$
• Right Child: $2i + 1$
• Parent: $\lfloor i/2 \rfloor$

Why Leave Index 0 Unused?

Simplified Arithmetic

In a 1-based index system, mathematical calculations for child and parent indices become more intuitive. Consider a 1-based array:

• For a node at index $i$, the left child is at index $2i$, and the right child is at index $2i + 1$.
• The parent of a node at index $i$ can be found at index $\lfloor i/2 \rfloor$.

This symmetry simplifies certain algorithms, especially during heap insertion and removal operations like `heapify`, where node swaps occur frequently.

In a 0-based index, these formulas are slightly altered:

• Left Child: $2i + 1$
• Right Child: $2i + 2$
• Parent: $\lfloor (i-1)/2 \rfloor$

The 1-based indexing removes the need for extra arithmetic operations like additions or subtractions, contributing to cleaner code and possibly fewer off-by-one errors.

Initialization Convenience

Using a 1-based index implies that the index directly corresponds with the level-order position of elements in the heap. This initialization might be more natural to understand, especially in educational or practical scenarios where the heap's position-like structure is emphasized.

Historical Reasons

Older programming languages, notably Fortran, used 1-based indexing by default. With Fortran's influence in numeric and scientific computing, many classical algorithms, including those for heaps, were designed with 1-based indexing in mind. Although many modern languages default to 0-based indexing, legacy conventions persist, particularly in instructional materials and algorithm textbooks.

Example: Max-Heapify Operation

Let's examine how the `max-heapify` operation benefits from 1-based indexing. This operation ensures the subtree rooted at index $i$ satisfies the max-heap property, assuming the binary trees rooted at the left and right children do as well.

Pseudocode (1-based Indexing)