Practice: Ranking Tournament Scores Without a Second Array

A scoreboard has room for its scores and nothing more; sort them in place.

Sorting in fixed memory is heapsort's job, and this exercise practises both of its phases by hand: build the max-heap bottom-up, then run the first extractions and keep track of the boundary between the heap and the sorted scores.

A scoreboard controller holds a tournament's five scores in an array with no room to spare: 61 84 47 90 73. Rank them, lowest first, with heapsort. First build the max-heap, sifting down each parent from the last one to the root, and write down the array. Then run two extractions and write down the array after each, marking which indices still belong to the heap.

Show the answer

The max-heap is 90 84 47 61 73, and after two extractions the array is 73 61 47 84 90, with the heap at indices 0 to 2 and the two highest scores in their final places. Five items put the last parent at index 5/2 − 1, rounded down to 1, so the build sifts down index 1 and then index 0. The trace shows each sift-down and each extraction, with end marking the last index of the heap.

Building the heap from five scores, then two extractions

Input61 84 47 90 73

Scores
1. 61
2. 84
3. 47
4. 90
5. 73end
Five scores. The build sifts down the parents at indices 1 and 0, and end marks the last index of the heap, which is still the whole array.
Sift 84
1. 61
2. 90
3. 47
4. 84
5. 73end
84 has children 90 and 73. 90 is the larger, so they swap.
Sift 61
1. 90
2. 84
3. 47
4. 61
5. 73end
61 at the root has children 90 and 47. It swaps with 90, then with 84, the larger of 84 and 73, and the array is a max-heap.
90 to index 4
1. 84
2. 73
3. 47
4. 61end
5. 90
The first extraction swaps 90 with 73. 90 stays at index 4, and 73 sifts down past 84.
84 to index 3
1. 73
2. 61
3. 47end
4. 84
5. 90
The second extraction swaps 84 with 61. 84 stays at index 3, and 61 sifts down past 73.

Result73 61 47 84 90

The root, 61, had to fall two levels, past 90 and then past 84, which is the step most often stopped one swap early. The first extraction placed 90 at index 4 and the second placed 84 at index 3. A function that runs the whole sort calls one sift-down with two bounds and prints the heap and the sorted part after each extraction.

practice_scores.pypy

def sift_down(scores: list[int], i: int, end: int) -> None:
    while 2 * i + 1 < end:
        child = 2 * i + 1
        if child + 1 < end and scores[child + 1] > scores[child]:
            child += 1
        if scores[i] >= scores[child]:
            return
        scores[i], scores[child] = scores[child], scores[i]
        i = child


def heapsort(scores: list[int]) -> None:
    n = len(scores)
    for i in range(n // 2 - 1, -1, -1):
        sift_down(scores, i, n)
    print("max-heap:", " ".join(map(str, scores)))
    for end in range(n - 1, 0, -1):
        scores[0], scores[end] = scores[end], scores[0]
        sift_down(scores, 0, end)
        print("heap", " ".join(map(str, scores[:end])), "| sorted", " ".join(map(str, scores[end:])))


scoreboard = [61, 84, 47, 90, 73]
heapsort(scoreboard)
print("ranked, lowest first:", " ".join(map(str, scoreboard)))

OutputRan with python:3.14.8-slim-trixie (Python 3.14.8)

max-heap: 90 84 47 61 73
heap 84 73 47 61 | sorted 90
heap 73 61 47 | sorted 84 90
heap 61 47 | sorted 73 84 90
heap 47 | sorted 61 73 84 90
ranked, lowest first: 47 61 73 84 90

Line 15 sifts within the whole array during the build, and line 19 sifts within the heap alone, bounded by end. The second and third lines of output are the two arrays the exercise asked for, split at the boundary. The sort needed no second array, only the index variables, which is what the scoreboard's memory allows.

← → move through sections and cards