Past exam of the year 1 of the computer science course of the University of Oxford / 2013 / Functional programming, design and analysis of algorithms / 6 / c / ii

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. HenceThe tight worst-case bound for this ordinary binary heap implementation isWhen 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.