Question

Modify Heapsort so that it stops after it finds the \(k\) largest keys in nonincreasing order. Analyze your algorithm, and show the results using order notation.

Short answer

The modified Heapsort algorithm that finds the \(k\) largest keys in nonincreasing order has the time complexity of \(O(n + k \log n)\), where \(n\) is the total number of keys.

Step-by-step solution

Modifying Heapsort

The first step is to modify the Heapsort. The modification includes running the first part of Heapsort which is heapifying the array, and then instead of extracting all elements, only extract \(k\) elements. To run the first part and build a max heap, go through all non-leaf nodes, starting from the last internal node, down to the root node, and perform the heapify operation. This will ensure that the largest element is at the root of the heap, which will be the first largest key.

Extracting the \(k\) largest keys

After building the max heap, the next step is to extract the \(k\) largest keys. To do this, perform the second part of Heapsort which is extracting the top element from the heap and then calling heapify, but only do this \(k\) times. Each time after top extraction, call heapify on the root again to bring the next largest element to the root, which can then be extracted in the next iteration.

Analyzing the Algorithm

During analysis, observe that building the max heap, which is done once, has a time complexity of \(O(n)\), where \(n\) is the total number of keys. After that, extraction of \(k\) largest keys is done \(k\) times, with each having a time complexity of \(O(\log n)\) because of the heapify operation. Therefore, the overall time complexity, using big-O notation, of the modified algorithm becomes \(O(n + k \log n)\) as the time complexities for creating the heap and extracting the \(k\) largest keys are added.