CS231 lecture notes, Fall 1998
Week 9, Wednesday

Using a stack to manage recursion
---------------------------------

In notes13.txt, we saw a way to use a stack to make a recursive
method iterative.

  public static int totalTree2 (Tree root) {
    Stack stack = new Stack ();

    stack.push (root);
    Tree tree;
    int total = 0;

    while (!stack.empty()) {
      tree = (Tree) stack.pop ();

      if (tree != null) {
        total += tree.value;
        stack.push (tree.right);
        stack.push ((tree.left);
      }
    }
    return total;
  }

We can do the same thing with a pre-order traversal:

  (transform the preceding code into a pre-order traversal).

What happens if we replace the stack with a queue?


The heap property
-----------------

A heap is a binary tree in which

1) the elements are comparable

2) no child is greater than its parent (may be equal)

A heap is not really an ADT, since it specifies something about the
implementation, rather than just the interface, but it is not quite
concrete, since there are several ways to implement one.

Maybe the best way to think about it is that heapness is a property
that a tree may or may not have.

We will study heaps from a couple of different angles:

1) how to implement one, using a couple of implementations

2) how to use one to implement an algorithm, like sorting

3) how to use one to implement an ADT, like a Priority Queue


First, let's implement one based on a tree representation similar
to the one we have been working with...

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

class Heap {
  public HeapNode root;
}

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

A heap is a tree with a sentinel that has the tree property.

Write a constructor for a new Heap, HeapNode

Write heap.isEmpty

Write print as an object method in the Heap class
(note that is is natural to put the recursive worker
method in HeapNode).


Questions for next time...

1) how do we insert something new?

2) how do we remove something?

3) how do we check for heapness?

4) how do we restore heapness if it is absent?