CS231 lecture notes, Fall 1998
Week 13, Friday

Section 8.5: Analysis of Priority Queue implementations
-------------------------------------------------------

We now have three implementations of a Priority Queue

1) linked list, items sorted
2) array, items unsorted
3) Heap, items half-sorted (partially ordered)

For each implementation, we can say whether a given operation takes

O(1)      constant time
O(n)      time proportional to the number of elements
O(logn)   time proportional to the log of the number of elements


	  insertion	       removal
list	  n		       1
array     1                    n
Heap      log n                log n         (assuming we can fix it)

So how long does it take to insert n items and them remove them all,
which is one way of sorting?

List implementation:

     n insertions:  1 + 2 + 3 + 4 + ... + n = n/2 (n-1) = O(n^2)
     n removes:     O(n)

Array implementation:

      same thing, the other way around

Heap implementation:

A little hard to figure, since the height of the tree is changing,
but often it is useful to derive an upper bound by making pessimistic
assumptions.

For example, if we assume that the height of the tree is always
log(n)... even when there are only two elements! ... then we get

     n insertions: n log n
     n removals:   n log n

     Total: O(n log n)    the factor of two does not change the
			  proportional behavior


WARNING:  so far we have been assuming that the tree is well
balanced, but that is not always true.  What if it starts getting
stringy, so that the height is proportional to the number of
elements?  What happens to our analysis?


Section 8.6: Traversals
-----------------------

Tree traversal is a common idiom, usually consisting of two parts,
the traversal, and some piece of work that you do at each node,
which is usually called visiting.

For example, in height, the visit consists of setting the node's
height, and it happens after we get back from the recursive calls.

  public static int height (Heap heap) {
    if (heap == null) return 0;

    // do the recursions
    int left = height (heap.left) + 1;
    int right = height (heap.right) + 1;

    // then "visit" the parent
    if (left > right) return left;
    return right;
  }

This is sometimes called a post-order traversal.

In the mirror example, we visit the parent (by swapping
its children, and then recurse:

  public static void mirror (Heap heap) {

    // base case
    if (heap == null) return;

    // swap the children
    Heap temp = heap.left;
    heap.left = heap.right;
    heap.right = temp;

    // mirror the children
    mirror (heap.left);
    mirror (heap.right);
  }

That's a pre-order traversal.  A third possibility is that we might
recurse on one of the children and then do something to the parent,
and then recurse on the other child.  That's an in-order traversal.

Finally, there are lots of hybrid methods (like insert and remove)
that do something before _and_ after the recursive calls.


8.11 -- Huffman Codes
---------------------

Step 1: Object design

HuffTree: usual tree things, with either a letter or a number
	  at each node

FreqTab: a frequency table, with a count for each letter

CodeTab: a mapping from letters to their Huffman codes

Huffman: a process object that encapsulates encoding and decoding

The instance variables for a Huffman are a HuffTree, a FreqTab
and a CodeTab.

The methods are

    1) build a FreqTab based on a sample String

    2) build a HuffTree based on the FreqTab

    3) build a CodeTab based on the HuffTree

    4) encode a String based on the CodeTab

    5) decode a coded String based on the HuffTree


How should we represent coded Strings?  We'll put them in
a class called Code and implement them as an array of
booleans.

What are the input Strings going to look like?  Let's stick
with all lower-case letters.

Development plan:

1) write Huffman and FreqTable, and test the first method,
   called buildFreqTab

2) write HuffTree and test the second method, buildHuffTree

3) write CodeTab and test the third method, buildCodeTab

4) write decode

5) write encode