Print the biggest K elements in a given heap in O(K*log(K))?

Question

Given the following problem , I'm not completely sure with my current solution :

Question :

Given a maximum heap with n elements , which is stored in an array A , is it possible to print all the biggest K elements in O(K*log(K)) ?

My answer :

Yes , it is , since searching an element requires O(log(K)) , hence doing that

for K elements would take O(K * log(K)) running time.

Answer 1

Searching for an element in a heap of size N is not O(K). First, it does not make sense that the time complexity for finding one element depends on the number of elements you are trying to extract (which is what K represents). Also, there is no such thing as searching in a heap — unless you count the standard look-at-every-element search in O(N).

However, finding the largest element in a heap is O(1) by design (I am obviously assuming that it's a max-heap, so the maximum element is at the top of the heap), and removing the largest element from a heap of size N is O(log(N)) (replace it with a leaf element, and have that leaf percolate back down the heap).

So, extracting K elements from a heap, and returning the heap of non-extracted elements, would take O(K·log(N)) time.

What happens if you extract K elements non-destructively from the heap ? You can do this by keeping a heap-of-heaps (where the value of a heap is the value of its maximum element). Initially, this heap-of-heaps contains only one element (the original heap). To extract the next maximum element, you extract the top heap, extract its top element (which is the maximum) and then reinsert the two sub-heaps back into the heap-of-heaps.

This grows the heap-of-heaps by one on every removal (remove one, add two), which means it will never hold more than K elements, and so the remove-one-add-two will take O(log(K)). Iterate this, and you get an actual O(K·log(K)) algorithm that does returns the top K elements, but is unable to return the heap of non-extracted elements.

Answer 2

This is possible in a max-heap because you are only printing elements from the tree, not extracting them.

Start by identifying the maximum element, which is located at the root node. Form a pointer to a node and add it to an otherwise empty "maximums" list. Then, for each of the k values, perform the following steps in a loop.

• Pop the maximal element from the list, taking O(1).
• Print its value, taking O(1).
• Insert each of the children of this maximal element to the list. Maintain sort when you insert them, taking O(log(size of list)) time. The maximum size of this list, since we are performing this loop k times, is branch-size*k. Therefore this step takes O(log(k)) time.

In total, then, the run time is O(klog(k)), as desired.