Skip to main content
Post Migrated Here from stackoverflow.com (revisions)
Post Made Community Wiki
Source Link
sgm
  • 139
  • 4

A heap is one example of the advantages to 1-based arrays. Given an index i, the index of i's parent and left child are

PARENT[i] = i ÷ 2

LCHILD[i] = i × 2

But only for 1-based arrays. For 0-based arrays you have

PARENT[i] = (i + 1) ÷ 2 - 1

LCHILD[i] = (i + 1) × 2 - 1

And then you have the property that i is also the size of the sub-array to that index (i.e. indices in the range [1,i]).

But in the end it doesn't matter, because you can make a 0-based array into a 1-based array by allocating one more element than normal, and ignoring the zeroth. Thus you can opt-in to get the benefits of 1-based arrays when appropriate, and keep the 0-based arrays for cleaner arithmetic in almost all the other situations.