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

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

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.

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

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.