// Heapsort sobre un std::vector, en el lugar. Usa un heap con el mayor en la raíz.
#ifndef HEAPSORT_H
#define HEAPSORT_H

#include <cstddef>
#include <utility>
#include <vector>

// Baja el elemento de i dentro de items[0, n). less(a, b): a va antes que b en el orden final.
// Devuelve cuántos niveles bajó.
template <typename T, typename Less>
std::size_t sift_down_max(std::vector<T>& items, std::size_t i, std::size_t n, Less less) {
    std::size_t levels = 0;
    while (true) {
        std::size_t left = 2 * i + 1;
        std::size_t right = 2 * i + 2;
        std::size_t largest = i;
        if (left < n && less(items[largest], items[left])) {
            largest = left;
        }
        if (right < n && less(items[largest], items[right])) {
            largest = right;
        }
        if (largest == i) {
            return levels;
        }
        std::swap(items[i], items[largest]);
        i = largest;
        levels++;
    }
}

// Construye de abajo hacia arriba: las hojas ya son heaps, y se empieza por el último padre.
// El índice baja hasta 0 sin pasar por debajo: size_t no tiene negativos.
// Devuelve el total de niveles que bajaron los elementos.
template <typename T, typename Less>
std::size_t build_max_heap(std::vector<T>& items, Less less) {
    std::size_t total = 0;
    for (std::size_t i = items.size() / 2; i > 0; i--) {
        total += sift_down_max(items, i - 1, items.size(), less);
    }
    return total;
}

template <typename T, typename Less>
void heapsort(std::vector<T>& items, Less less) {
    build_max_heap(items, less);
    for (std::size_t end = items.size(); end > 1; end--) {
        // El mayor de items[0, end) pasa a su lugar definitivo.
        std::swap(items[0], items[end - 1]);
        sift_down_max(items, 0, end - 1, less);
    }
}

#endif