A code fragment to check whether the entries in an array form a heap.

int check_heap( a, k, n) {

//       Check whether the elements in the subtree starting with
//       element k in an array of length n form a heap.  Return
//       1 if they do and 0 if they do not.

   if ( k > n ) cout << " ouch" << endl;

   left_kid_index  = 2*k;
   right_kid_index = 2*k + 1;
   
   if ( left_kid_index  > n ) return 1; // Say yes if this is a leaf.
   if ( right_kid_index > n ) {
      if ( a(left_kid_index < a(k) ) return 0;
      else return 1;
   }

   else {
      both_ok =  check_heap( a, left_kid, right_kid, n)  // This is one if both
                *check_heap( a, left_kid, right_kid, n) ;// subtrees are ok.
      if (     ( a(left_kid)  < a(k) ) 
           and ( a(right_kid) < a(k) ) 
           and ( both_ok = 1 )  )      return 1;
      else return 0;

}