0
$\begingroup$

I am having trouble with coming up for a suitable algorithm for this question. A max-heap is essentially visualized as a binary tree not a binary search tree. Also the runtime of the algorithm must depend only on the number of elements in the output. I was thinking of doing a preorder traversal on the max heap. While doing the preorder traversal, if the value of a node is less than the given value x, we return to the previous recursive call. All child nodes in a max heap are less than the parent node. Otherwise we output current node and recur on the children.

I am not sure however if the runtime of this algorithm depends only on the number of elements in the output.

Anybody have other suggestions/thoughts? Thanks.

Improve this question
$\endgroup$
3

1 Answer 1

Reset to default
0
$\begingroup$

The algorithm you're describing is basically correct.

To summarize in one sentence: "If the current value is less than $x$, turn back."

The reason it has the desired time complexity is because the set of the nodes you are visiting is precisely:

  • the root node
  • all the nodes which are direct descendants of the nodes in the output (since every node has no more than two children, there are no more than $2k$ of these)

So the total number of times the body of your function gets executed is no more than $2k+1$.

Improve this answer
$\endgroup$
1
  • $\begingroup$ I see! Thank you for clarifying. $\endgroup$
    – Sandy
    Commented Aug 6, 2020 at 0:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.