cs230 Lecture Notes
Week 10 Friday

Hand back exams.

Correction, page 121, in isComplete, last clause should be

    if (left != null && right != null)


Vectors
-------

at any time, a vector has a size and a capacity

capacity: space (number of elements) that have been allocated
	  for objects

size: number of objects that are actually in the array

There are many methods for adding and removing elements.

They all have different semantics, different effects on
size and capacity, and different possibilities for error.

You have to figure it out!  Yes, I know the documentation is
hard to read.

HINT: capacity is always >= size,  anything that increases
      size also increases capacity

HINT: casual users really never have to worry about capacity
      the only reason to care is if the performance of the
      Vector is not good enough and you think reserving
      capacity will help

Making things worse
-------------------

Along with worrying about size and capacity, we also have to keep
track of empty trees.

Two choices:  

1) use null to represent empty trees, but then you
   can't allow users to put null objects in the
   tree as cargo

   (an empty tree is not the same thing as a node that
   contains a null object)

2) allow null objects in the tree and use a special
   value to represent an empty tree


Homework 9
----------

The HEAP:  a tree that is complete, and that has the heap property

Heap property:

     an empty tree is considered a heap

     anything is considered larger than nothing

     the root is larger than anything in either subtree

     the subtree have the heap property

Exercise: write a method that traverses a tree and checks the
	  heap property


Heaps are good implementations of priority queues

1) easy to find the node with highest priority

2) after removing something we can restore the heap property quickly

3) when we add something we can restore the heap property quickly


Steps for implementing

1) sketch algorithm graphically

2) see what operations we need to perform

3) choose a tree implementation and implement any operations

4) implement the heap operations