Question

Let's suppose that you have a binary min-heap with S elements. Please write an an algorithm that will find all the elements that are in the heap that are smaller than a given value X. Please make sure that the time complexity of the algorithm that you propose has to be O(K), where is the number of elements smaller than X that is in the heap.

Please type answer if you can

Answer 1

Solution

current_index denotes the index of the element in the min heap we are currently working with.

Start the algorithm from the root node, and initialize current_index = 0

if(current_index != NULL)

{

if(element(current_index)>X)

{

Return,since the element at current_index and all its descendants are skipped as these are greater or equal to X

}

else

{

Print the element at the current_index

Follow the process again with current_index = current_index.leftChildIndex

Follow the process again with current_index = current_index.rightChildIndex

}

}

Logic:

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. We utilize this property to search for the required elements as follows:

Start testing the elements from the root node of the heap. If root element is >X it means none of the elements of the heap is smaller than X

current_index is 0 , since we are testing the root node. If element at current_index<X, the element is printed and we check the root elements in left and right subtree of current element.

We stop searching descendants of a node as soon as the value of the element is greater than or equal to X.

Since we stop searching descends of the node if the element in node is > or equal to X so the time complexity of the given algorithm is O(k), where k is the number of element smaller than X.