TADM2E 4.15

Part A

It helps to know what you can't do first. The (2n-3) algorithm is a simple scan through the array with a max1 and max2 variable, comparing each newly encountered element against max2 and possibly max1. The worst case scenario is:

• 1 compare to add the first two elements
• 2 compares for each of the remaining n-2 elements

This gives a total of 2n-3 compares, though on randomized data you would expect an average of n+log2(n) compares. As per the problem description, worst case performance knocks linear scan out of the picture.

Similarly, we could heapify the entire array, which is guaranteed to take less than or equal to 2n compares. The first element in the resulting array is the largest, and the second largest will be either the second or third element in the array. This results in a compare count of <= 2n+1, which for randomized data and reasonably sized n will be substantially less than 2n-3. However, the worst case still makes this an unacceptable solution.

One correct answer is to use the tournament algorithm to find the 2nd largest element. In the tournament algorithm we pair up sets of two elements and then find the winner, then recursively do the same with the winners, like a knockout football game. The second largest number can be any one in the list of numbers which lost to the winner. Check the winner in the losers group (lost to the best element). This can be done in n+log(n) time complexity.

While not strictly a heap, the structure of the tournament solution is somewhat heaplike and likely what Skiena had in mind for a valid solution.

Part B

One possibility for third largest key is to heapify for <= 2n compares. The largest key will be the first array element. The second largest key will be either array element 2 or 3, requiring one compare to determine. The third largest key will be among array elements 3, 4, 5, 6, and 7 (if the second largest key was array element 2). Thus, the third largest element requires additional four compares to determine. The total compare count would be <= 2n+5.

There is also a tournament solution. The first and second largest are found in n+log(n) time as above, while the third largest can be picked as the best remaining loser to either the first or second.

Tradeoffs

While tournament has the best reliable compare count, it comes at the expense of additional storage space to store the wins and losses. The heapify option, while having a larger compare count, is in-place and in a real implementation this may make it worth using.

The trivial 'scan and compare' approach is by far the most likely approach that any real piece of software is likely to use. Its average compare count on random data is going to be similar to that of heapify, but without the complex logic and nested loops. Further, it won't have to reorder the data or keep additional storage around. It also has excellent cache locality.