To keep track of which array positions hold valid info:

  1. either each node has info saying which of its children exist.

  2. or, each array position has info saying if it contains valid info.

With complete trees, these problems go away: if there are N nodes, they occupy the first N array positions.

  1. keeping track of N tells us which array positions contain valid info.

  2. a new value must go in position N+1. If we delete a value: we must reorganize the heap to fill the gap.

  3. for(i=0;i<N;i++){ process node in position i; } results in a level-by-level traversal.