cs230 Lecture Notes
Week 10, Monday

Homework 8 is due today.  Exam #2 is Thursday.

For next Tuesday, read Sections 18.6 through 18.11

Today's topics
--------------

1) array representation of trees

2) hw07 solutions

3) exam review


Array representation of a tree
------------------------------

Lay the tree out sideways with the root at index 1.

The index of the left child is always  2*i
The index of the right child is always 2*i + 1

Advantages

1) no need to store references, just compute indices

2) can also compute parent node: i/2 (truncated)

3) constant time access to any element of the tree

Problems

1) we no longer have the nice behavior of a linked
   data structure, the ability to pass around parts
   of a tree using a single reference

2) it's even more difficult to maintain appropriate
   encapsulation of the tree implementation

Nevertheless, the array tree is a particularly good
choice to implement a HEAP!


The heap
--------

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

Completeness: filled in from top to bottom, left to right

Heap property:

     an empty tree is considered a heap

     the root is larger than anything in either subtree

     the subtrees have the heap property

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


public class Tree {
    Object[] array;
































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