**Note:** You should always justify your answers. Whenever you are asked to describe an algorithm, you should present three things: the algorithm, a proof of its correctness, and a derivation of its running time.

Suppose you want to make statements of the form "It was warmer on day $i$ than on the $k$ previous days". Your input is the (average) temperatures on day $1,\ldots,n$ stored in an array $A$ of size $n$. Design a linear-time algorithm (using a stack) that computes for every day $i$ the $k$ from the statement above (and stores it in an array B). For instance, input $A = [14, 7, 31, 15, 20, 40]$ should result in output $B = [0, 0, 2, 0, 1, 5]$.

Analyze the running time. You do not need to prove correctness. *Note: This exercise is tricky. If you can't figure out what to store in the stack, ask for a hint.*

(*Reminder: Justify your answer, even if the question is a simple yes/no question.*)

(a) [3 points] Illustrate the execution of HeapSort on the following input: $(7,13,25,42,17,36,16)$. Show every step that changes the array. (*Remark: You do not need to give drawings of heaps in your solution; giving the arrays is sufficient.*)

(b) [1 point] What is the running time of HeapSort on an array $A$ of length $n$ that is already sorted?

(c) [1 point] Is an array that is in sorted order a min-heap?

(*Reminder: Justify your answer, even if the question is a simple yes/no question.*)

(a) [1 point] Is the sequence $\langle 42, 9, 25, 7, 1, 21, 22, 2, 4, 3 \rangle$ a max-heap?

(b) [1 point] Where in a max-heap might the smallest element reside, assuming that all elements are distinct?

(c) [3 points] Devise a divide-and-conquer algorithm for building a heap stored in an array $A[1..n]$ in $O(n)$ time. You should derive the running time using a recurrence, and argue correctness.