CS231 lecture notes, Fall 1998
Week 11, Wednesday

Exogenous vs. endogenous
------------------------

1) start with endogenous integers -- finish this implementation
   by Friday

2) replace with exogenous Student objects that
   implement the Comparable abstract class (for Monday)

Recursive algorithm for remove
------------------------------

Need to return two values, the removed item and the updated
heap.

Solution: make an instance variable called removed_item.
Call sequence looks like:

    root = remove (root);
    System.out.println (root.removed_value + " removed");

Return itself is easy:

1) move the root value into removed_value.
2) reheapify and return the tree

Reheapification is the tricky part:

1) choose the larger child and move the value into the parent
2) reheapify the robbed child (if the child is a leaf, delete it)


Algorithm for insert
--------------------

Thinking recursively, the base case is easy:  inserting an
integer into a null heap means creating a new Heap node
and returning a reference to it.

Can we figure out by looking at the two children which subtree
the new node should attach to?

1) if both are null, then LEFT
2) if only one is null, choose it
3) if neither is null, choose the one with lower rank

Rank is the minimum distance from a node to a leaf node.

rank(null) = 0
rank(h) = 1 + min (rank(h.left), rank(h.right))

Look at some examples to see that this is correct.

Once we have chosen which child gets the new element, the
basic recursive step is:

      heap.left = insert (heap.left, newItem);

This is a common recursive idiom, meaning "replace my left
child with the tree that results from the insertion."

Finally, we need to check that the top node of the modified
subtree does not exceed the parent.  If it does, we just
swap the parent and the precocious child.

-------------------------------------------------------------------
Source: Webster's Revised Unabridged Dictionary (1913) [web1913] 

      precocious \Pre*co"cious\, a. [L. praecox, -ocis, and
         praecoquus, fr. praecoquere to cook or ripen beforehand; prae
         before + coquere to cook. See 3d Cook, and cf. Apricot.]
         1. Ripe or mature before the proper or natural time; early or
            prematurely ripe or developed; as, precocious trees. [R.]
            --Sir T. Browne.

         2. Developed more than is natural or usual at a given age;
            exceeding what is to be expected of one's years; too
            forward; -- used especially of mental forwardness; as, a
            precocious child; precocious talents.
------------------------------------------------------------------

Can we prove that this algorithm maintains the heap property?

1) increasing the parent clearly poses no danger with respect to
   the unaffected child

2) decreasing the top node of the precocious child seems dangerous,
   except that we know there can be only one value in the subtree
   greater than the parent -- the new one.




Development plan
----------------

1) start with Tree.java, rename Heap.java

2) keep the tree-building code in main

3) write isHeap, and check it using a couple of hand-made
   heaps.

4) write printHeap, which prints the nodes in level order,
   with each level on a new line

5) write remove, and test it like so...

    printHeap (root);
    boolean b = isHeap (root);
    System.out.println (b);

    root = remove (root);
    System.out.println (root.removed_value + " removed");
    
    printHeap (root);
    b = isHeap (root);
    System.out.println (b);

6) modify height (from the quiz) so that it calculates rank.

7) create a simplified insert that just puts things into the
   tree without regard for rank.

8) modify insert so it swaps with the modified child on the
   way back up the recursive call stack.


------------

To get you started, and to facilitate debugging, here is
my version of printHeap:

  public static void printHeap (Heap heap) {

    int height = height (heap);

    for (int i = 0; i<height; i++) {
      printLevel (heap, i, 0);
      System.out.println ("");
    }
  }

  public static void printLevel (Heap heap, int level, int sofar) {
    if (sofar == level) {
      if (heap == null) {
	System.out.print ("n ");
      } else {
	System.out.print (heap.value + " ");
      }

    } else if (heap != null) {
      printLevel (heap.left, level, sofar+1);
      printLevel (heap.right, level, sofar+1);
    }
  }