= Solution
Store the <array> as a <binary heap> with <min-heap> order. Build it bottom-up by sifting down internal nodes in reverse order, rather than inserting all $n$ values one at a time. The sum of subtree heights is $O(n)$, so construction costs $\Theta(n)$. Then perform $i$ minimum extractions: output the root, move the last remaining entry to the root, and sift it down to restore the <heap order>.
Each extraction returns the smallest remaining key, so the outputs are the $i$ smallest keys in increasing order. For a heap of current size $s$, an extraction takes $O(\log(s+1))$ time. Hence
$$
T_2(n,i)=O\!\left(n+\sum_{j=0}^{i-1}\log(n-j+1)\right)
=O(n+i\log n).
$$
The tight worst-case bound for this ordinary <binary heap> implementation is
$$
\boxed{T_2(n,i)=\Theta(n+i\log n).}
$$
When the extraction term is substantial, worst-case extractions follow root-to-leaf paths of logarithmic length; when $i$ is small, the linear construction already dominates. The bound stays valid at $i=n$, since $\log(n!)=\Theta(n\log n)$. Building by $n$ separate insertions would lose the linear construction bound and is unnecessary.
Back to article page
