Heaps
Table of contents
Submit your solutions to the following questions as a PDF on Gradescope.
Range searching in heaps
Suppose we want to print out all the values less than a given value in a binary min-heap. The given value might not be in the heap. Assume the array representation of a binary min-heap with the first element stored at index 0.
- Write pseudocode for an efficient algorithm to solve this problem. In the general case, your algorithm should not examine every element in the heap. Make sure your algorithm does not change the heap.
- What is the worst case input for your algorithm? Describe both the state of the heap as well as the given value.
- Give a tight asymptotic runtime bound for the worst case. Briefly explain your answer.
Pseudocode guidelines
Pseudocode means that you don’t have to write every line in Java with correct syntax. English explanations of operations are acceptable. In general, you may substitute English for any constant-time operation.
The following example is not acceptable pseudocode.
scan the list and count all elements less than x
The following example is acceptable pseudocode.
while the list has elements:
increment the counter if the current element is greater than x
move to the next element of the list
The idea is that you don’t have to give all the nitty-gritty coding details, but you should demonstrate a clear understanding of what your algorithm does and where those nitty-gritty details would have to go. To indicate blocks of code, either use braces {} or indentation levels.