BUILD-MAX-HEAP(A)

1. A. heap-size = A .length

2. for i = [A.length/2J downto 1

3. MAX-HEAPIFY (A, i)

Shows an example of the action of BUILD-MAX-HEAP.

Problem 1. Why do we want the loop index i in line 2 of BUILD-MAX-HEAP to decrease from [A.length/2] to 1 rather than increase from 1 to [A. length/2]?

Problem 2.

The operation HEAP-DELETE (A, i) deletes the item in node i from heap A. Give an implementation of HEAP-DELETE that runs in 0(lg n) time for an n-element max-heap.

Problem 3.

What is the running time of QUICKSORT when all elements of array A have the same value?

Problem 4.

Banks often record transactions on an account in order of the times of the transac-tions, but many people like to receive their bank statements with checks listed in order by check number. People usually write checks in order by check number, and merchants usually cash them with reasonable dispatch. The problem of converting time-of-transaction ordering to check-number ordering is therefore the problem of sorting almost-sorted input. Argue that the procedure INSERTION-SORT would tend to beat the procedure QUICKSORT on this problem.

Problem 5.

Why do we analyze the expected running time of a randomized algorithm and not its worst-case running time?

Problem 6.

What is the smallest possible depth of a leaf in a decision tree for a comparison sort?

Problem 7.

Which of the following sorting algorithms are stable: insertion sort, merge sort, heapsort, and quicksort? Give a simple scheme that makes any sorting algorithm stable. How much additional time and space does your scheme entail?

Problem 8.

Explain why the worst-case running time for bucket sort is Θ(n²). What simple change to the algorithm preserves its linear average-case running time and makes its worst-case running time O(n lg n)?

A1. Use the figure above as a model, illustrate the operation of heap sort on the array A = [5, 10, 7, 25, 8, 4]. Show all intermediate steps how the heap is transformed.