CS231 lecture notes, Fall 1998
Week 10, Monday

Program development
-------------------

Some steps for program development

1) choose classes and sketch their basic interactions

2) write basic methods you know you're going to need
   (like constructors and printers)

3) test simple mechanisms for manipulating the new objects
   (create a print a few trees)

4) at the same time you're doing all that, sketch
   algorithms for the hard things, and write any helper
   methods that you will want


Classes
-------------

public class Sorter {
  public static void main (String[] args) {
  }
}

class Heap {
  public HeapNode root;
}

class HeapNode {
  public int value;
  public HeapNode left, right;
}

Algorithms
----------

Insertion:

In iterative language, we want to traverse the tree
from top to bottom to find the path from the root to
the "next available spot"

The next available spot is defined as

the left-most non-null child of the leftmost leaf
in the lowest level that contains a leaf

How can we possibly find it?

Useful to define something called "rank", which is
the shortest distance from a given node to the
"frontier"

To find the shortest distance to the beach, always
choose the child with the lower rank.

Now, once we have installed a new node in the right spot,
you have to traverse the same path from the new node
to the root, restoring the heap property as you go.

All of this is easiest to do recursively, in part because
you can do the repair work on the way back from the
recursion.  In other words, retracing your steps is
free.

An alternative is to use a Stack to keep track of what
you have visited.

Removal:

Write a method called reheapify that restores a heap
to its former glory, assuming that it is a proper
heap in every regard except that it is headless.

Now all you have to do is remove the top element and 
then reheapify.

Checking:

Often it is useful (for debugging) to check a tree
for heapness.  You might want to write a method that
does it.


Development
-----------

What are some intermediate steps you can use to develop
this thing?


0) write height and rank and check them on some trees
   where you know the answer

1) build a tree by hand and check it for heapness,
   by printing it and by using the checker

2) remove things from it (since remove is easier than
   insert) and check to see if reheapify works

2.5) add some things to the tree, but don'y worry about
     the heap property; just make sure they get put in the
     right place.

3) add something to it and check it (again, by printing	
   and using the checker)