Question

Provide an algorithm that solves the following problem:

input: a binary heap B, an integer value x

output: all keys in B that are smaller than x

Constraint: your algorithm must run in time O(K), where K is the number of keys output.

Explain why your algorithm has the required runtime behaviour.

(Use pseudocode or C++, or any informal (but clear) description. You are free to choose any kind of representation of binary heaps, as long as it was mentioned in class.)

Answer 1

Do a preorder traversal of the heap.

At each step,

1.if the element looked at has value ≥ m, do not explore that subtree any further;

2.otherwise print the element and continue the preorder traversal in that subtree

See the code snippet for only printing small elements than x (Assuming Min Heap and it is already created),

Complexity is O(k) 
--> doing a preorder traversal so that we will be avoiding elements greater than required element

void MinHeap::printSmallerNodes(int x, int pos = 0){
   if (pos >= heap_size) // if position is > heap size its invalid so return
      return; 
   if (arr[pos] >= x) { // if value arr[pos] > x that means we are traversing element that is greater than our required so neglect it do return
      return;
   }
   cout<<arr[pos]<<" "; // print current element (it prints is ascending order as we are starting from 0 position that is top node of min heap that is the least of array given
   printSmallerNodes(x, left(pos)); // span left
   printSmallerNodes(x, right(pos)); // span right
}