## 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

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)