Heap Sort

# Heap Sort

Zerethon Official Sample `heap-sort`, version 1.2.0, C++ (GCC 14).

- `heap_sort.cpp` / `heap_sort.hpp` — the algorithm (the same steps as this sample's C code)
- `main.cpp` — entry file: a short demonstration
- `test_heap_sort.cpp` — checks; set it as the entry file to run them (or Run ▾ → Run tests)

Run compiles the entry file together with every other `.cpp` file except other programs (files
whose name starts with `main` or `test_`).

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).
#include "heap_sort.hpp"
#include <utility>

static void sift_down(std::vector<int> &a, int root, int hi) {
    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]) return;
        std::swap(a[root], a[child]);
        root = child;
    }
}

void heap_sort(std::vector<int> &a) {
    const int n = static_cast<int>(a.size());
    for (int i = n / 2 - 1; i >= 0; i--) sift_down(a, i, n - 1);
    for (int end = n - 1; end > 0; end--) {
        std::swap(a[0], a[end]);
        sift_down(a, 0, end - 1);
    }
}

// Heap Sort (Zerethon Official Sample: heap-sort 1.2.0).
#pragma once
#include <vector>

void heap_sort(std::vector<int> &a);

#include <algorithm>
#include <iostream>
#include <vector>
#include "heap_sort.hpp"

static void print(const char *label, const std::vector<int> &a) {
    std::cout << label << '[';
    for (size_t i = 0; i < a.size(); i++) std::cout << (i ? ", " : "") << a[i];
    std::cout << "]\n";
}

int main() {
    const std::vector<int> numbers = {38, 27, 43, 3, 9, 82, 10, 27};
    print("Before: ", numbers);
    std::vector<int> result = numbers;
    heap_sort(result);
    print("After:  ", result);
    std::vector<int> expected = numbers;
    std::sort(expected.begin(), expected.end());
    std::cout << "Same as std::sort: " << std::boolalpha << (result == expected) << '\n';
}

// Checks for heap_sort. To run them, set this file as the entry file
// (the ▶ button next to it in Files) and press Run.
#include <algorithm>
#include <iostream>
#include <utility>
#include <vector>
#include "heap_sort.hpp"

// Deterministic pseudo-random integers in [-50, 49] (the same as the other languages' checks).
static std::vector<int> numbers(long long seed, int count) {
    std::vector<int> out;
    for (int i = 0; i < count; i++) {
        seed = (seed * 1103515245LL + 12345LL) % 2147483648LL;
        out.push_back(static_cast<int>(seed % 100) - 50);
    }
    return out;
}

int main() {
    std::vector<std::vector<int>> cases = {{}, {1}, {2, 1}, {1, 2, 3}, {3, 2, 1}, {5, 1, 5, 1, 5}, {-3, 0, -1, 2}};
    for (const auto &[seed, size] : std::vector<std::pair<int, int>>{{1, 10}, {2, 50}, {3, 200}}) cases.push_back(numbers(seed, size));

    for (size_t i = 0; i < cases.size(); i++) {
        std::vector<int> result = cases[i], expected = cases[i];
        heap_sort(result);
        std::sort(expected.begin(), expected.end());
        if (result != expected) {
            std::cerr << "heap_sort: wrong result for case " << i + 1 << " (length " << cases[i].size() << ")\n";
            return 1;
        }
    }
    std::cout << "All " << cases.size() << " checks passed." << std::endl;
}