Print the biggest K elements in a given heap in O(K*log(K))?
algorithm, big-o, heap, search, tree
Solution
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.
Problem
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.