Past exam of the year 1 of the computer science course of the University of Oxford / 2017 / Functional programming, design and analysis of algorithms (resit) / 8 / a / Solution

Build a max-heap, then repeatedly swap its root with the last element of the active prefix, shrink that prefix and restore heap order by heapify down. A zero-based implementation is

for i = floor(n/2)-1,...,0:
    siftDown(A,i,n)
for end = n-1,...,1:
    swap A[0],A[end]
    siftDown(A,0,end)

siftDown(A,i,end) repeatedly exchanges entry i with its larger child while the child lies below end and has a larger key. The suffix beyond end is already sorted and never touched again. For the specified input, key stages of heapsort are

The final array is $[1,2,3,4,5]$. Bottom-up construction takes $O(n)$ time because there are progressively fewer nodes at each greater subtree height; the extractions give worst-case $O(n\log n)$ time and constant auxiliary storage for iterative sifting.