NOTE:

These are a little sketchy...I'll fill in details 'soon'.

Assumptions:  A is an array whose elements are indexed 1..size

Definitions:

   A heap is a data structure typically stored in tree form:

                      root
                       |
                 --------------
                /              \
               /                \
            lchild            rchild
              |                  |
           --------          --------
          /        \        /        \
       lchild    rchild  lchild    rchild

   A heap has the property that a parent node (element of the tree
   with children) has a value greater than or equal to both of its
   children.  So:

              5
             / \
            /   \
           4     3
          / \   / \
         3   2 1   1

   is a heap but:

              5
             / \
            /   \
           4     3
          / \   / \
         3   5 1   6

   is not.   Since tree's are hard to store in a computer, we can
   store this in an array as:

      ------------------------------------------------------------------
      | root | lchild | rchild | llchild | lrchild | rlchild | rrchild |
      ------------------------------------------------------------------

   Or, for the example above:

      -----------------------------
      | 5 | 4 | 3 | 3 | 2 | 1 | 1 |
      -----------------------------

Relationships:

   For a heap stored in an array:

   Given a parent (root), the left child of that parent is found
   by the formula:

      left = 2*parent

   The right child of the parent is given by:

      right = 2*parent + 1 = left + 1

   The parent of a given child is:

      parent = child / 2

   assuming integer division.

Add a root to the heap:
begin AddRoot ( newroot, size )
   active = newroot
   child = left child of active
   if (child exists)
      if (child's sibling exists) and (A[child] < A[sibling])
         child = right child of active
      end if

      while (child exists) and (A[active] < A[child])
         Swap(A[active], A[child])
         active = child
         child = left child of active
         if (child's sibling exists) and (A[child] < A[sibling])
            child = right child of active
         end if
      end while
   end if
end AddRoot

Build a heap from some arbitrary array:
begin BuildHeap ( )
   beginning at the parent of the last child
   and moving down to the first element
      AddRoot(current, size)
   end loop
end BuildHeap

Sort an arbitrary array:
begin HeapSort ( )
  BuildHeap( )
  beginning at the end of the array
  and moving down to the second element
     Swap(A[first], A[current element])
     decrement the array's size
     AddRoot(first, size)
  end loop
end HeapSort