Give an algorithm with worst-case running time of O(k log k) to print the k biggest elements in a n-element max-heap (binary heap stored in an array) without modifying the max-heap (or if you do modify it, restore it to the input heap within the given time bound). For example, if the max-heap is A = [100, 88, 44, 66, 77, 11, 22, 5, 55] and k = 5, the output could be 100, 88, 66, 77, 55 (the order in which the algorithm prints does not matter). Do not assume n = O(k). Here n can be much larger than k.

Let a be the array in which elements of the max heap are stored.

Number of nodes in a binary tree of height h = 2^h+1-1

We know that in case of the max heap the k largest elements exist between the root and the maximum height k-1 in the binary max heap.

Number of nodes in the binary tree of height k-1 = 2^h+1-1 = 2^k-1+1-1 = 2^k - 1

So the k largest elements exist among the front  2^k - 1 elements in the array.

So we can search the array from index 0 to index  2^k - 2.

The required algorithm is shown below:

get_k_Biggest_Elements(Array_a)

integer m =  2^k - 1??????

Create a new array b of size m.

The elements from index 0 to index 2^k - 2 in array a are copied to array b.

  BUILD-MAX-HEAP(b)

  for i := 1 to k

Heap-Extract-Max(b)

  MAX-HEAPIFY //This step results in O(log k) complexity

end for

Step-by-step explanation

Explanation And Complexity Analysis:

Contruct a new max heap using the front 2^k - 1???????elements from the given array(which is a max heap)

Note the height of the new max heap is k.

The maximum element is present in the root node.

We extract the maximum element from the heap and convert it back to max heap. This step has a complexity O(log k).

Since the previous step is performed k times, hence total time complexity = k *  O(log k) =  O(klogk)