CS231 lecture notes, Fall 1998
Week 9, Wednesday

Program structure
-----------------

1) all local variables

   good encapsulation (can prove things)

   lots of parameter-passing

   can inhibit division into methods

   can inhibit error-handling

2) global static variables

   less parameter passing

   breakdown in encapsulation

3) global instance variables

   good compromise -- methods share data, but data is
   still encapsulated in objects

   can create multiple process objects simultaneously!

Two kinds of encapsulation (method, object)

    (what are the two kinds of invariant?)


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 heap 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?