Heap Sort

# Heap Sort

Zerethon Official Sample `heap-sort`, version 1.1.0, PHP 8.4.

- `heap_sort.php` — the algorithm, as shown in Zerethon Tools
- `main.php` — entry file: a short demonstration
- `test_heap_sort.php` — 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

<?php

// Heap Sort (Zerethon Official Sample: heap-sort 1.1.0).
// The algorithm as shown in Zerethon Tools.

function sift_down(array &$a, int $lo, int $hi): void {
    $root = $lo;
    while (2 * $root + 1 <= $hi) {
        $child = 2 * $root + 1;
        if ($child + 1 <= $hi && $a[$child] < $a[$child + 1]) $child++;
        if ($a[$root] < $a[$child]) {
            [$a[$root], $a[$child]] = [$a[$child], $a[$root]];
            $root = $child;
        } else return;
    }
}
function heap_sort(array $a): array {
    $n = count($a);
    for ($i = intdiv($n, 2) - 1; $i >= 0; $i--) sift_down($a, $i, $n - 1);
    for ($end = $n - 1; $end > 0; $end--) {
        [$a[0], $a[$end]] = [$a[$end], $a[0]];
        sift_down($a, 0, $end - 1);
    }
    return $a;
}

<?php

require __DIR__ . '/heap_sort.php';

$a = [38, 27, 43, 3, 9, 82, 10, 27];
echo 'Before: [' . implode(', ', $a) . "]\n";
$result = heap_sort($a);
echo 'After:  [' . implode(', ', $result) . "]\n";
$expected = $a;
sort($expected);
echo 'Same as sort(): ' . ($result === $expected ? 'true' : 'false') . "\n";

<?php

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

require __DIR__ . '/heap_sort.php';

/** Deterministic pseudo-random integers in [-50, 49] (the same as the Python checks). */
function numbers(int $seed, int $count): array
{
    $out = [];
    for ($i = 0; $i < $count; $i++) {
        $seed = ($seed * 1103515245 + 12345) % 2 ** 31;
        $out[] = $seed % 100 - 50;
    }

    return $out;
}

$cases = [[], [1], [2, 1], [1, 2, 3], [3, 2, 1], [5, 1, 5, 1, 5], [-3, 0, -1, 2]];
foreach ([[1, 10], [2, 50], [3, 200]] as [$seed, $size]) {
    $cases[] = numbers($seed, $size);
}

foreach ($cases as $a) {
    $result = heap_sort($a);
    $expected = $a;
    sort($expected);
    if ($result !== $expected) {
        fwrite(STDERR, 'heap_sort([' . implode(', ', array_slice($a, 0, 6)) . "...]) is wrong\n");
        exit(1);
    }
}

echo 'All ' . count($cases) . " checks passed.\n";