Heap Sort

# Heap Sort

Zerethon Official Sample `heap-sort`, version 1.2.0, Python 3.12.

- `heap_sort.py` — the algorithm, as shown in Zerethon Tools
- `main.py` — entry file: a short demonstration
- `test_heap_sort.py` — checks; set it as the entry file to run them

This project is your own copy. Changing it never changes the official sample.
See the algorithm animated: https://tools.zerethon.com/heap-sort-visualizer

"""Heap Sort (Zerethon Official Sample: heap-sort 1.2.0)."""


def heap_sort(a):
    n = len(a)

    def sift_down(lo, hi):
        root = lo
        while 2 * root + 1 <= hi:
            child = 2 * root + 1
            if child + 1 <= hi and a[child] < a[child + 1]:
                child += 1
            if a[root] < a[child]:
                a[root], a[child] = a[child], a[root]
                root = child
            else:
                return

    for i in range(n // 2 - 1, -1, -1):
        sift_down(i, n - 1)
    for end in range(n - 1, 0, -1):
        a[0], a[end] = a[end], a[0]
        sift_down(0, end - 1)
    return a

from heap_sort import heap_sort

numbers = [38, 27, 43, 3, 9, 82, 10, 27]
print("Before:", numbers)
result = heap_sort(list(numbers))
print("After: ", result)
print("Same as sorted():", result == sorted(numbers))

# Checks for heap_sort. To run them, set this file as the entry file
# (the ▶ button next to it in Files) and press Run.
from heap_sort import heap_sort


def numbers(seed, count):
    """Deterministic pseudo-random integers in [-50, 49]."""
    out = []
    for _ in range(count):
        seed = (seed * 1103515245 + 12345) % 2**31
        out.append(seed % 100 - 50)
    return out


cases = [[], [1], [2, 1], [1, 2, 3], [3, 2, 1], [5, 1, 5, 1, 5], [-3, 0, -1, 2]]
cases += [numbers(seed, size) for seed, size in ((1, 10), (2, 50), (3, 200))]

for case in cases:
    got = heap_sort(list(case))
    assert got == sorted(case), f"heap_sort({case[:6]}...) = {got[:6]}..."

print(f"All {len(cases)} checks passed.")