# COMP582 Module 7 Problems

\$30.00

## Description

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