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

Algorithm to get all keys less than x:

The binary heap representation I have used to explain is an array based min binary heap,

For an index i,  

a. The left child is given by index 2*i + 1,

b. The right child is given by index 2*i + 2

For a min-Heap each node has lesser key than both its child, unless its a leaf node.

The min-heap array is represented by heapArr

We use a queue, which is initially empty.

Then index 0 is pushed in the queue.

While queue is not empty

i = front of the queue

pop the queue

if i >= heapSize ( the number of elements in heap )

continue;

if heapArr[ i ] is less than x ( the integer input ) then,

cout << heapArr[ i ]; ( print it or store it in a new vector )

push the left and right child indexes in queue ( push 2*i + 1 and 2*i + 2 in queue ).

Finally after the queue becomes empty, all keys less than x have been printed.

Time Complexity of the algorithm is O( k ), where k is number of keys in the heap less than x.