Range search in a max-heap

Question

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.

Сергей Макеев · Accepted Answer

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$.

Range search in a max-heap

One Answer

Add your own answers!

Ask a Question