1  Binary trees, full binary trees, and complete binary trees

Basic binary tree facts:

1. A binary tree is a tree with 0, 1, or 2 child nodes (or subtrees) to a node.

2. A leaf is a node that has no child nodes.

3. A full binary tree is a binary tree such that every non-leaf node has two children.

4. A complete binary tree is a binary tree that is full except for its lowest level, and such that all leaves (in the lowest level) are positioned as far left as they can be.

   Here is a full binary tree (tilt your head 90 degrees to the left):

                   1
               2
                   3
      root 7         
                   4
               5
                   6
   

   Here is a complete binary tree (that is not full):

                   
               2
                   3
      root 7         
                   4
               5
                   6
   

5. A complete binary tree can be stored as an array.

Also, given the position of a child node, the position of the parent node can be found as:

Here this is integer division, meaning that the remainder is thrown away after division. The result of the division has no decimal fraction.

2  Heaps

A heap is a complete binary tree such that the value in every parent node is at least as large as the values in the child nodes.

Here is a heap:

                
            3
                2
   root 7         
                4
            6
                5

3  Inserting a new value into a heap

1. Add the new value as a new leaf as far left as it can go. This keeps the heap tree a complete binary tree.

   For example, in the tree above, adding, say, 10 to the heap gives:

                   10
               2
                   3
      root 7         
                   4
               5
                   6
   

2. Obviously, the 10 has to be repositioned to make the tree a heap again (with all parents at least as large as their children).

   To do this ``reheapify upwards'' as follows:

   1. Exchange the 10 with 2, its parent.
   2. Exchange the 10 with 7, its new parent.

   Now the tree looks like this:

                   2
               7
                   3
      root 10        
                   4
               5
                   6
   

   The tree is again a heap.

3. For tree node values stored in an array A,
   1. Add the value to be inserted to the end of A and increment the size.
   2. Let i be the location in A of the added value.

   3. Compare the value at i with the value at (i - 1)/2 in the array (the parent node).

      If the parent is smaller, exchange.

      Set i to the location of the parent.

   4. Keep doing the last step until either no exchanges occur or i has become 0.

4  Removing the root of a heap

The trick is to restore the heap nature of the tree (all parents are at least as large as their children) after removing the root. The process is:

1. Replace the root value with the value in the rightmost leaf of the tree, and delete that leaf.

   For example in this tree:

                   1
               7    
                   6
           10        
                   4
               5
                   2
   

   the replacement will give:

                   
               7    
                   6
           1        
                   4
               5
                   2
   

2. The new root value 1 is not at least as large as its children.

   To make the tree a heap again, ``reheapify downwards'' as follows:

   1. Exchange the 1 with the larger of its children, the 7.
   2. Then exchange the 1 with the larger of its new children, the 6.

   The result is:

                   
               6   
                   1
           7        
                   4
               5
                   2
   

   which is a heap again.

3. For tree node values stored in an array A:
   1. Replace the root value (at position 0 in the array) with the value in the rightmost leaf of the tree (which is the last item in the array). Decrement the size of the array.

   2. Let i be 0, the location of the root in the array.

   3. Compare the value at location i with the values at locations 2i + 1 and 2i + 2 (the locations of the children).

      If one of these last two values is larger than the value at i, then

      1. Exchange values
      2. Reset i to the location of the child that was exchanged with.

   4. Keep doing the last step until no exchanges occur or both 2i + 1 and 2i + 2 move beyond the array.

5  The heap sort

Heaps can be used to perform a quite efficient sort. Here is how it works, given an array A:

1. Insert all the entries in A into a heap.
2. Replace all of the entries in A from the last to the first with values repeatedly deleted from the heap.