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

I found the other answers confusing so I decided to explain it with an actual example heap. Assume original heap is size N and you want to find the kth largest elements, This solution takes O(klogk) time and O(k) space.

    10 
   /  \
  5    3 
 / \   /\
4   1 2  0
Original Heap, N = 7 

Want to find 5th largest element. k = 5 Note: In the new heap, you need to store the pointer to the original heap. This means, you do not remove or change the original heap. The original heap is read-only. Therefore, you never have to do any operations that requires O(logN) time.

Let x' be the pointer to value x in the original heap.

1st Iteration: Get root node's pointer into new heap

Step 1: Add pointer to node 10

 10'
 New Heap, size = 1, root = 10', root->left = 5, root right->3

Print the 1st largest element = 10

2nd iteration: Refer to the original heap and insert both it's children into the new heap. (Storing the pointers to them and not the value themselves). The reason you want to store the pointer is so that you can access them in O(1) from the original heap later to search for their children instead of O(N) to search for where that value is located in the original heap.

Step 2a: Look for left child of root node of new heap from the original heap. Add a pointer for the left child (in this case, 5') to the new heap.

  10' 
 /
5'
New Heap, size = 2, root = 10', root->left = 5, root right->3

Step 2b: Look for right child of root node of new heap from the original heap. Add a pointer for the left child (in this case, 3') to the new heap.

  10' 
 / \
5'  3'
New Heap, size = 3, root = 10', root->left = 5, root right->3

Step 2c: Remove root node from New Heap. (Swap max node with right most leave, remove root node and bubble down current root to maintain heap property)

  10'   swap    3'  remove & bubble   5'    
 / \     =>    / \       =>          /
5'  3'        5'  10'               3'
New Heap, size = 2, root = 5', root->left = 4, root right->1

Print the 2nd largest element = 5

Step 3a: Look for left child of root node of new heap from the original heap. Add a pointer for the left child (in this case, 4') to the new heap.

  5'
 / \
3'  4'
New Heap, size = 3, root = 5', root->left = 4, root right->1

Step 3b: Look for right child of root node of new heap from the original heap. Add a pointer for the left child (in this case, 1') to the new heap.

    5'
   / \
  3'  4'
 /
1'
New Heap, size = 4, root = 5', root->left = 4, root right->1

Step 3c: Remove root node from New Heap. (Swap max node (5') of New Heap with its right most leave from the original heap (1') from the New Heap, remove root node and bubble down current root to maintain heap property)

    5'        Swap     1' remove & bubble     4'
   / \         =>     / \       =>           / \
  3'  4'            3'   4'                 3'  1'
 /                 / 
1'                5'
New Heap, size = 3, root = 4', root->left = NULL, root right->NULL

Print the 3rd largest element = 4

Step 4a & Step 4b does nothing since root node does not have any children in this case from original heap.

Step 4c: Remove root node from New Heap. (Swap max node with right most leave, remove root node and bubble down current root to maintain heap property in New Heap)

    4'        Swap     1' remove & bubble     3'
   / \         =>     / \       =>           / 
  3'  1'            3'   4'                 1'  
New Heap, size = 2, root = 3', root->left = 2, root right->0

Print the 4th largest element = 3

Step 5a: Look for left child of root node of new heap from the original heap. Add a pointer for the left child (in this case, 2') to the new heap.

     3'
    / \
   1'  2'
New Heap, size = 3, root = 3', root->left = 2, root right->0

Step 5b: Look for right child of root node of new heap from the original heap. Add a pointer for the left child (in this case, 0') to the new heap.

     3'
    / \
   1'  2'
  /
 0'
New Heap, size = 4, root = 3', root->left = 2, root right->0

Step 5c: Remove root node from New Heap. (Swap max node (3') with its right most leave from the original heap (which is 0') in the New Heap, remove root node and bubble down current root to maintain heap property in New Heap)

     3'    Swap        0'  Remove & Bubble      2'
    / \     =>        / \         =>           / \
   1'  2'            1'  2'                   1'  0'
  /                 /
 0'                3'
New Heap, size = 3, root = 2', root->left = NULL, root->right = NULL

Print the 5th largest element = 2

Finally, since we have gone through k iterations, k = 5. We can now extract the root element's value from the new heap. In this case, the value is 2. Therefore, we have found the kth largest value from the original heap.

Time Complexity, T(N,k) = O(klogk) Space Complexity, S(N,k) = O(k)

Hope this helps!

Soon Chee Loong,

University of Toronto.

Answer 2

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 3

It is a simple and elegant algorithm to get first k elements of a max heap in k log(k) time.

steps:-

1.construct another max heap name it auxiliary heap
2.add root element of main heap to auxiliary heap
3.pop out the element from auxiliary heap and add it's 2 children to the heap
4.do step 2 and 3 till k elements have been popped out from auxiliary heap. Add the popped element's children to the auxiliary heap.

Answer 4

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.

Answer 5

Indeed, it is too easy, extracting the max element is O(log(N)) where N is the size of the heap. and N≠K.

I will add that searching for a random element is O(N) and not O(Log(N)), but in this case we want to extract the max.