Problem#2 Part A) Reconsider the problem described in Exercise 1.24 (Page 63).

We might attempt to adapt the basic idea in the Heapsort routine to find the second-largest entry. Explain how to change the heapSort() code on Page 190 to find the second-largest entry; of course, for full credit you should eliminate unnecessary work wherever possible.

Note: An overview of how your algorithm works is REQUIRED. You are not required to provide specific pseudocode (however, you may wish to do so anyway, if you are unsure whether your overview truly explains precisely what you plan to do). If you are using the support routines (constructHeap(), fixHeap(), deleteMax(),...) verbatim, you can just rely on the code in the book, of course. 4.2B: Based on your algorithm in 4.2A, determine the time complexity of your code (you may use O() notation rather than giving a precise function; of course, explain how you arrived at your answer). If you employ one of the Heapsort support routines without making changes to it, you can just use the text's estimate of the complexity of that subroutine. Note that O(0.5*n^3 - 2n) would be an inferior estimate to just saying O(n^3), so (as always) do try to give the most *succinct* function which (accurately) describes the growth. Note: It would be a mistake to infer that using these sorting routines for the Chapter 1 problems will lead to superior solutions -- they may well be inferior to the more straightforward approaches. The point of these problems is to force you to explore how our sorting algorithms work, which (hopefully!) will lead to a deeper understanding of the inner mechanisms.

1.24 Write an algorithm to find the second largest element in a set containing n entries. How many comparisons of elements does your algorithm do in the worst case? (It is possible to do better than 2n 3; we will consider this problem again.) 1.24 Write an algorithm to find the second largest element in a set containing n entries. How many comparisons of elements does your algorithm do in the worst case? (It is possible to do better than 2n 3; we will consider this problem again.)