### Heap Question

A complete binary tree of height h  has all the levels filled through level h-1, and the leaves on level h are filled left to right.
In other words,

1. All nodes at level h-2 and above have 2 children each, and
2.When a node at level h-1 has children, all nodes to its left at the same level have 2 children each, and
3.When a node at level h-1 has one child, it is a left child

A heap is a complete binary tree with the following recursive definition:
1) empty
OR
2) whose root contains a search key greater than or equal to the search key in each of its children, AND
3) whose subtrees are also heaps

For example,  this tree is a heap:                                            This tree is not a heap.  Notice the subtree starting at 50:
100                                                                            100
/        \                                                                        /       \
70           85                                                               50       60
/     \       /      \                                                               /    \     /
50    40   80      1                                                         55   45  35
/  \
9    2

#### Part 1

The idea behind inserting into a heap is
1) Create a new node at level h ( in the appropriate spot) and store the new value there.  Note that  now you no longer have a heap.
2) Then,  compare  this value with the value of its parent.  Swap values if out of order.
3) Repeat this "bubble up" process until you have a heap again.

Draw a picture of the heap created by inserting the following data :   10  5  8  15  3  12  14  20   9

#### Part 2

A very useful implementation for a heap is an array.  The root is stored at index 0,  and its children are stored at index 1 and 2.  For any node at index i,  its left
child is at index [2*i  + 1]  and its right child is at index [2*i + 2] ( note that this even works for the root).   A size variable would hold how much data is in the array.

Draw what the array would look like for the heap you drew above.

#### Part 3

Implement the method public void heapInsert(Object o) to insert a piece of data into our heap based on the algorithm above.

Assumptions:
1)  Assume that the objects in the heap support the method compareTo().
2)  The Heap class has instance variables size and Object[] items.
3)  Assume there is a method ensureCapacity()  just like we had for our SimpleArrayList class.

Hint:  If you have the index of a node ( e.g.   index i ),  the index of the parent is [ (i - 1) / 2].

### Language Question

Consider the problem of recognizing whether a particular string is in the language L

L = { w\$w' |  w is a possibly empty string of characters other than \$,  w' = reverse(w) }

For example, the strings "a\$a",   "\$",  and "abc\$cba" are in L,  but "Ab\$Ab", "xw\$WX" , and "abc\$cb" are not.

1) Write a method that is passed in a string and returns true or false based on whether the argument is in this language.  Use a Stack to solve the problem.

2) Solve the same problem recursively, without a stack.