Respuesta :
Answer:
Starting from root, recursively traverse the min-heap. Once we find a key with value less than our X, we know that every key in subtree of that key will be also smaller than our X. Otherwise, we should keep traversing.
Explanation:
The complexity of this algorithm will be O(N) where N is the number of keys in our min-heap.
A Min-Heap is a complete binary tree in which the value in each internal node is smaller than or equal to the values in the children of that node.
What is Min heap?
Mapping the elements of a heap into an array is trivial if a node is stored an index k, then its left child is stored at index 2k + 1 and its right child at index 2k + 2.
The idea is to do a preorder traversal of the given Binary heap. While doing preorder traversal, if the value of a node is greater than the given value x, we return to the previous recursive call.
Because all children nodes in a min-heap are greater than the parent node. Otherwise, we print the current node and recur for its children.
The algorithm is below,
FIND_SMALLER_NODES (node, Key x){if (node.value >= x){/* Skip this node and its descendants, as they are all &
gt;= x . */return;}print(node.value);
if (node.left != NULL)FIND_SMALLER_NODES(node.left, x);if (node.right != NULL)FIND_SMALLER_NODES(node.right, x);}
If a subtree's root has a value that is greater than or equal to x, then, by definition of a min-heap, all of its descendants will also have values greater than or equal to x.
The algorithm need not explore deeper than the items it's traversing, hence it is alright.
Learn more about "min-heap" here:
brainly.com/question/25295434
