Answer the Questions from the Review Sheets For Midterms 1 & 2. In addition:

Heaps

• What is the Max Heap Property? How does it differ from the BST property?
• What is the Big-O runtime of each of the heap algorithms we discussed in class?
  
• Trace each step of the buildMaxHeap operation (diagram and array) on the following:

Diagram                    Array

                        A = [4, 9, 7, 18, 2, 3]

1.

2.                        A = [ ___ , ___, ___, ___, ___, ___ ]   

3.                        A = [ ___ , ___, ___, ___, ___, ___ ]   

4.                        A = [ ___ , ___, ___, ___, ___, ___ ]   

• Trace heapInsert on the below Max Heap and the value 35. Show diagram and array at each step below:

Diagram                    Array

1.                        A = [21, 11, 13, 2, 9]

2.                        A = [ ___ , ___, ___, ___, ___, ___ ]   

3.                        A = [ ___ , ___, ___, ___, ___, ___  ]   

4.                        A = [ ___ , ___, ___, ___, ___, ___  ]   

• Trace heapSort on the following heap. Show diagram and array at each step below:

Diagram                    Array

1.                        A = [100, 90, 80, 70]

2.                        A = [ ___ , ___, ___, ___ ]   

3.                        A = [ ___ , ___, ___, ___ ]   

4.                        A = [ ___ , ___, ___, ___ ]   

Trace the merge sort algorithm on the following array of values:

[50, 2, 12, 17, 6, 1, 4, 52]

[ ___, ___, ___, ___ ] [ ___, ___, ___, ___ ]

[ ___, ___ ]    [ ___, ___]   [ ___, ___] [ ___, ___ ]

[ ___ ]    [ ___ ] [ ___ ]    [ ___ ] [ ___ ]    [ ___ ] [ ___ ]    [ ___ ]

[ ___, ___ ]    [ ___, ___]   [ ___, ___] [ ___, ___ ]

[ ___, ___, ___, ___ ] [ ___, ___, ___, ___ ]

[ ___, ___, ___, ___, ___, ___, ___, ___ ]

Write the pseudocode for the mergeSort operation. Note that you do not need to write the helper function merge.

mergeSort(A, low, high)

What is the Big O run-time of MergeSort in the best, worst and average case?

Best: O (                            )

Average: O (                            )

Worst: O (                            )

Give an example of a sorting algorithm that we have studied in this class that falls into each of the following categories:

An in-place sorting algorithm:

A comparison-based sorting algorithm:

A divide-and-conquer sorting algorithm:

A parallel sorting algorithm: