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.