Heinze grew up in Matawan New Jersey. At age fourteen he won a scholarship to Blair Academy in Warren County where he graduated in 1973. He subsequently won a Bodman Foundation scholarship that enabled him to attend Amherst College where he received his B.A. in 1977 graduating Magna Cum Laude. He attended graduate school at the University of California Berkeley receiving his M.A. in 1980 and his Ph.D.