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
    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.

    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.