Heap Sort

// Heap Sort (Zerethon Official Sample: heap-sort 1.1.0).
// The algorithm as shown in Zerethon Tools.
public class HeapSort {
    static void siftDown(int[] a, int lo, int hi) {
        int root = lo;
        while (2 * root + 1 <= hi) {
            int child = 2 * root + 1;
            if (child + 1 <= hi && a[child] < a[child + 1]) child++;
            if (a[root] < a[child]) {
                int t = a[root]; a[root] = a[child]; a[child] = t;
                root = child;
            } else return;
        }
    }
    static void heapSort(int[] a) {
        int n = a.length;
        for (int i = n / 2 - 1; i >= 0; i--) siftDown(a, i, n - 1);
        for (int end = n - 1; end > 0; end--) {
            int t = a[0]; a[0] = a[end]; a[end] = t;
            siftDown(a, 0, end - 1);
        }
    }
}

// Checks for heapSort. To run them, set this file as the entry file
// (the ▶ button next to it in Files) and press Run.
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class HeapSortTest {
    /** Deterministic pseudo-random integers in [-50, 49] (the same as the Python checks). */
    static int[] numbers(long seed, int count) {
        int[] out = new int[count];
        for (int i = 0; i < count; i++) {
            seed = (seed * 1103515245L + 12345L) % 2147483648L;
            out[i] = (int) (seed % 100) - 50;
        }
        return out;
    }

    public static void main(String[] args) {
        List<int[]> cases = new ArrayList<>(List.of(
            new int[] {}, new int[] {1}, new int[] {2, 1}, new int[] {1, 2, 3}, new int[] {3, 2, 1},
            new int[] {5, 1, 5, 1, 5}, new int[] {-3, 0, -1, 2}));
        cases.add(numbers(1, 10));
        cases.add(numbers(2, 50));
        cases.add(numbers(3, 200));

        for (int[] c : cases) {
            int[] result = c.clone();
            HeapSort.heapSort(result);
            int[] expected = c.clone();
            Arrays.sort(expected);
            if (!Arrays.equals(result, expected)) {
                System.err.println("heapSort(" + Arrays.toString(Arrays.copyOf(c, Math.min(6, c.length))) + "...) = " + Arrays.toString(result));
                System.exit(1);
            }
        }
        System.out.println("All " + cases.size() + " checks passed.");
    }
}

import java.util.Arrays;

public class Main {
    public static void main(String[] args) {
        int[] numbers = {38, 27, 43, 3, 9, 82, 10, 27};
        System.out.println("Before: " + Arrays.toString(numbers));
        int[] result = numbers.clone();
        HeapSort.heapSort(result);
        System.out.println("After:  " + Arrays.toString(result));
        int[] expected = numbers.clone();
        Arrays.sort(expected);
        System.out.println("Same as Arrays.sort(): " + Arrays.equals(result, expected));
    }
}

# Heap Sort

Zerethon Official Sample `heap-sort`, version 1.1.0, Java 25.

- `HeapSort.java` — the algorithm, as shown in Zerethon Tools
- `Main.java` — entry file: a short demonstration
- `HeapSortTest.java` — checks; set it as the entry file to run them

Every `.java` file is compiled together before the entry file's class runs.

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