Problem $6($Heap$-$find operation$)$

Let H be a heap storing n elements. We want to find the set of all elements in H whose keys are

less than or equal to the given key k $.$

Example: given the heap on p$.163$ and $k=7,$ we would return the four elements with keys

$\{4,5,6,7\},$ in some order.

a$)$ Find an $O(m)$ time algorithm for this $f$ ind $(H,k)$ operation, where $m$ is the number of elements

returned. Give an English description as well as detailed pseudocode.

Hint: you can use stacks or queues to help you, as we did for Breadth$-$First$-$Search.

b$)$ Prove that your algorithm is correct. Meaning, that it returns all the desired elements, and only

the desired elements.

Problem $6($Heap$-$find operation$)$

Let H be a heap storing n elements. We want to find the set of all elements in H whose keys are

less than or equal to the given key $k.$

Example: given the heap on p$.163$ and $k=7,$ we would return the four elements with keys

$\{4,5,6,7\},$ in some order.

a$)$ Find an $O(m)$ time algorithm for this find $(H,k)$ operation, where m is the number of elements

returned. Give an English description as well as detailed pseudocode.

Hint: you can use stacks or queues to help you, as we did for Breadth$-$First$-$Search.

b$)$ Prove that your algorithm is correct. Meaning, that it returns all the desired elements, and only

the desired elements.