1 The following array of current size 10 represents a heap structure:

1	2	3	4	5	6	7	8	9	10	11
97	76	61	42	54	59	31	23	17	44

The tree diagram of this heap is shown below:



a. (5 points) Insert a new value 86 into the heap. Draw the new heap when done. [Increase the heap size from 10 to 11 place 86 initially into slot 12 of the array, then perform upheap to restore the heap conditions.] Show the resulting array.


b. (10 points) Start again with the original heap of 10 elements. Show the result after each swap of two passes of HEAPSORT. Note: After one pass 97 is in position 10 and the values in positions 1 .. 9 again form a heap.

1	2	3	4	5	6	7	8	9	10
97	76	61	42	54	59	31	23	17	44

You may have extra space.

2. (5 points) Write a recursive function

int CountRange(Node* root, int low, int high);

Last Updated: May 26, 1997 9:47 pm by