Heap Sort

# Heap Sort

Zerethon Official Sample `heap-sort`, version 1.1.0, Node.js 22.

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

function heapSort(a) {
    const n = a.length;
    const siftDown = (lo, hi) => {
        let root = lo;
        while (2 * root + 1 <= hi) {
            let 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;
        }
    };
    for (let i = (n >> 1) - 1; i >= 0; i--) siftDown(i, n - 1);
    for (let end = n - 1; end > 0; end--) {
        [a[0], a[end]] = [a[end], a[0]];
        siftDown(0, end - 1);
    }
    return a;
}

module.exports = { heapSort };

const { heapSort } = require('./heap_sort');

const numbers = [38, 27, 43, 3, 9, 82, 10, 27];
console.log(`Before: [${numbers.join(', ')}]`);
const result = heapSort([...numbers]);
console.log(`After:  [${result.join(', ')}]`);
const expected = [...numbers].sort((x, y) => x - y);
console.log(`Same as sort(): ${result.join() === expected.join()}`);

// Checks for heapSort. To run them, set this file as the entry file
// (the ▶ button next to it in Files) and press Run.
const assert = require('assert');
const { heapSort } = require('./heap_sort');

/** Deterministic pseudo-random integers in [-50, 49]. */
function numbers(seed, count) {
    const out = [];
    for (let i = 0; i < count; i++) {
        seed = (seed * 1103515245 + 12345) % 2 ** 31;
        out.push((seed % 100) - 50);
    }
    return out;
}

const cases = [[], [1], [2, 1], [1, 2, 3], [3, 2, 1], [5, 1, 5, 1, 5], [-3, 0, -1, 2]];
for (const [seed, size] of [[1, 10], [2, 50], [3, 200]]) cases.push(numbers(seed, size));

for (const c of cases) {
    const got = heapSort([...c]);
    assert.deepStrictEqual(got, [...c].sort((x, y) => x - y), `heapSort([${c.slice(0, 6)}...])`);
}

console.log(`All ${cases.length} checks passed.`);