Module 7 Problems
1. [5 pts] Show that the build_heap algorithm has O(nlog(n)) upper bound
2. [5 pts] Show the binary max heap array resulting from using the standard
build_heap algorithm on this input sequence.
4 2 7 9 12 1 3 0 10 11
3. [5 pts] Show the binary max heap array resulting from using the Floyd
heapify algorithm on the same sequence from problem 2.
4. [15 pts] What is the array from problem 2 after a single delMax operation?
5. [20 pts] Write a pseudocode function to sort using an array-implemented
heap.
Note: Your algorithm must be done completely in-place. That is, your
algorithm can only
use O(1) extra space.
6. [20 pts] What is the (worst case) complexity of your method in problem 5?
7. [30 pts] Define the l-median of a sorted sequence of numbers of size N as
the
the number at index floor((N-1)/2), where the indexing starts at 0.
Intuitively, the l-median is the true median when N is odd. If N is even,
then the l-median is the maximum of smallest N/2 elements of the sorted
sequence.
Example 1
2 9 -1 7 Input list
-1 2 7 9 Sorted input list
l-median index = floor((4-1)/2) = 1
l-median = Sorted[1] = 2
Example 2:
2 9 -1 7 55 Input list
-1 2 7 9 55 Sorted input list
l-median index = floor((5-1)/2) = 2
l-median = Sorted[2] = 7
The problem:
Write (in pseudocode) a function that keeps a running l-median of
stream of numbers.
Using Eample 2 above input stream
2 9 -1 7 55
Your function should produce:
2 2 2 2 7
You do not have to worry about space. You may assume that the doubling
algorithm is employed for whatever data structures you want.
Problem Hint: consider using 2 priority queues, 1 Min, 1 Max as your main
data
structure. You will then need to implement 2 operations on this data structure:
1. insert(val): insert a value into the data structure
2. show_lmedian(): show the current median
Your implementation should have these time complexities:
In the requirements that follow, n is the # of data elements seen so far.
Time complexity for insert(val): O(log(n))
Time complexity for show_lmedian(): O(1)
