// Medidor de tiempos del curso. Compilar con -O2 y sin sanitizers.
#ifndef BENCH_H
#define BENCH_H

#include <algorithm>
#include <chrono>
#include <vector>

// Corre fn `reps` veces y devuelve la mediana en segundos.
template <typename Fn>
double median_seconds(int reps, Fn fn) {
    std::vector<double> times;
    times.reserve(reps);
    for (int i = 0; i < reps; i++) {
        auto start = std::chrono::steady_clock::now();
        fn();
        auto stop = std::chrono::steady_clock::now();
        times.push_back(std::chrono::duration<double>(stop - start).count());
    }
    std::sort(times.begin(), times.end());
    return times[times.size() / 2];
}

// Evita que el compilador borre un cálculo cuyo resultado no se usa.
template <typename T>
void keep(const T& value) {
    volatile T sink = value;
    (void)sink;
}

#endif

// Construir un min-heap de dos formas, contando comparaciones. Los conteos no dependen de la máquina.
#include <algorithm>
#include <cmath>
#include <cstddef>
#include <iomanip>
#include <iostream>
#include <numeric>
#include <random>
#include <string>
#include <vector>

#include "heapsort.h"
#include "int_heap.h"

namespace {

std::vector<int> make_input(const std::string& order, int n) {
    std::vector<int> items(n);
    std::iota(items.begin(), items.end(), 0);
    if (order == "desc") {
        std::reverse(items.begin(), items.end());
    } else if (order == "azar") {
        std::mt19937 generator(13);
        std::shuffle(items.begin(), items.end(), generator);
    }
    return items;
}

long count_pushes(const std::vector<int>& items) {
    IntHeap heap;
    for (int item : items) {
        heap.push(item);
    }
    heap.check_invariants();
    return heap.comparisons();
}

// build_max_heap con el orden al revés da un min-heap: la raíz es la menor.
long count_bottom_up(std::vector<int> items, std::size_t* levels = nullptr) {
    long comparisons = 0;
    std::size_t total = build_max_heap(items, [&](int a, int b) {
        comparisons++;
        return a > b;
    });
    if (levels != nullptr) {
        *levels = total;
    }
    return comparisons;
}

// Cuántos nodos de un árbol perfecto tienen altura h, y cuánto pueden bajar en total.
void print_levels(int k) {
    int n = (1 << (k + 1)) - 1;
    std::cout << "\nArbol perfecto con n = " << n << ", entrada descendente\n";
    std::cout << " altura  nodos  bajan como maximo\n";
    long total = 0;
    for (int h = 0; h <= k; h++) {
        long nodes = 1L << (k - h);
        total += nodes * h;
        std::cout << std::setw(7) << h << std::setw(7) << nodes << std::setw(19) << nodes * h << "\n";
    }
    std::size_t real = 0;
    count_bottom_up(make_input("desc", n), &real);
    std::cout << "suma: " << total << ", niveles que bajaron de verdad: " << real << "\n";
}

}  // namespace

int main() {
    std::cout << "        n  orden  abajo-arriba  /n    n pushes  /n  log2n\n";
    for (int n : {1023, 16383, 262143, 1048575}) {
        for (const std::string order : {"asc", "azar", "desc"}) {
            std::vector<int> items = make_input(order, n);
            long bottom_up = count_bottom_up(items);
            long pushes = count_pushes(items);
            std::cout << std::setw(9) << n << std::setw(7) << order << std::setw(14) << bottom_up
                      << std::fixed << std::setprecision(2) << std::setw(6) << double(bottom_up) / n
                      << std::setw(10) << pushes << std::setw(6) << double(pushes) / n
                      << std::setprecision(1) << std::setw(5) << std::log2(n) << "\n";
        }
    }
    print_levels(9);
    return 0;
}

// Sigue un min-heap paso a paso: el arreglo después de cada operación.
#include <iostream>

#include "int_heap.h"

namespace {

void print(const char* label, int value, const IntHeap& heap) {
    std::cout << label << " " << value << ": [";
    const char* separator = "";
    for (int item : heap.items()) {
        std::cout << separator << item;
        separator = " ";
    }
    std::cout << "]\n";
}

}  // namespace

int main() {
    IntHeap heap;
    for (int value : {5, 3, 8, 1, 4}) {
        heap.push(value);
        heap.check_invariants();
        print("push", value, heap);
    }
    int least = heap.top();
    heap.pop();
    heap.check_invariants();
    print("pop ", least, heap);
    return 0;
}

// ¿Cuánto salta cada algoritmo? Anota cada lectura y escritura del arreglo, y simula con ellas una
// cache pequeña: 32 KB, líneas de 64 bytes, cada línea en un único lugar posible (correspondencia directa).
// Es un conteo sobre un modelo, no una medición de la cache de esta máquina.
#include <algorithm>
#include <cstddef>
#include <cstdint>
#include <iomanip>
#include <iostream>
#include <numeric>
#include <random>
#include <vector>

namespace {

class CacheModel {
public:
    CacheModel() : tags_(lines_in_cache, -1) {}

    // position es el número del int dentro de la memoria simulada.
    void touch(std::size_t position) {
        std::int64_t line = static_cast<std::int64_t>(position / ints_per_line);
        std::int64_t& tag = tags_[static_cast<std::size_t>(line) % lines_in_cache];
        accesses_++;
        if (tag != line) {
            misses_++;
            tag = line;
        }
    }
    long accesses() const { return accesses_; }
    long misses() const { return misses_; }

private:
    static constexpr std::size_t ints_per_line = 64 / sizeof(int);
    static constexpr std::size_t lines_in_cache = 32 * 1024 / 64;
    std::vector<std::int64_t> tags_;
    long accesses_ = 0;
    long misses_ = 0;
};

void sift_down(std::vector<int>& items, std::size_t i, std::size_t n, CacheModel& cache) {
    while (true) {
        std::size_t left = 2 * i + 1;
        std::size_t right = 2 * i + 2;
        std::size_t largest = i;
        cache.touch(i);
        if (left < n) {
            cache.touch(left);
            if (items[largest] < items[left]) {
                largest = left;
            }
        }
        if (right < n) {
            cache.touch(right);
            if (items[largest] < items[right]) {
                largest = right;
            }
        }
        if (largest == i) {
            return;
        }
        std::swap(items[i], items[largest]);
        i = largest;
    }
}

void modeled_heapsort(std::vector<int>& items, CacheModel& cache) {
    for (std::size_t i = items.size() / 2; i > 0; i--) {
        sift_down(items, i - 1, items.size(), cache);
    }
    for (std::size_t end = items.size(); end > 1; end--) {
        cache.touch(0);
        cache.touch(end - 1);
        std::swap(items[0], items[end - 1]);
        sift_down(items, 0, end - 1, cache);
    }
}

// Mergesort de abajo hacia arriba. El arreglo auxiliar va después del original en la memoria simulada.
void modeled_mergesort(std::vector<int>& items, CacheModel& cache) {
    const std::size_t n = items.size();
    std::vector<int> buffer(n);
    std::size_t source_at = 0;
    std::size_t target_at = n;
    for (std::size_t width = 1; width < n; width *= 2) {
        for (std::size_t low = 0; low < n; low += 2 * width) {
            std::size_t mid = std::min(low + width, n);
            std::size_t high = std::min(low + 2 * width, n);
            std::size_t a = low;
            std::size_t b = mid;
            std::size_t out = low;
            while (a < mid || b < high) {
                bool take_b;
                if (a < mid && b < high) {
                    cache.touch(source_at + a);
                    cache.touch(source_at + b);
                    take_b = items[b] < items[a];
                } else {
                    take_b = a == mid;
                    cache.touch(source_at + (take_b ? b : a));
                }
                cache.touch(target_at + out);
                buffer[out++] = take_b ? items[b++] : items[a++];
            }
        }
        items.swap(buffer);
        std::swap(source_at, target_at);
    }
}

}  // namespace

int main() {
    std::cout << "        n  algoritmo     accesos       fallos  fallos/n\n";
    for (int n : {1000, 10000, 100000, 1000000, 4000000}) {
        std::vector<int> input(n);
        std::iota(input.begin(), input.end(), 0);
        std::mt19937 generator(13);
        std::shuffle(input.begin(), input.end(), generator);

        std::vector<int> items = input;
        CacheModel heap_cache;
        modeled_heapsort(items, heap_cache);
        if (!std::is_sorted(items.begin(), items.end())) {
            return 1;
        }
        items = input;
        CacheModel merge_cache;
        modeled_mergesort(items, merge_cache);
        if (!std::is_sorted(items.begin(), items.end())) {
            return 1;
        }
        std::cout << std::fixed << std::setprecision(2);
        std::cout << std::setw(9) << n << "   heapsort" << std::setw(12) << heap_cache.accesses() << std::setw(13)
                  << heap_cache.misses() << std::setw(10) << double(heap_cache.misses()) / n << "\n";
        std::cout << std::setw(9) << n << "  mergesort" << std::setw(12) << merge_cache.accesses() << std::setw(13)
                  << merge_cache.misses() << std::setw(10) << double(merge_cache.misses()) / n << "\n";
    }
    return 0;
}

// Comparaciones de heapsort según la entrada. Los conteos no dependen de la máquina.
#include <algorithm>
#include <cmath>
#include <iomanip>
#include <iostream>
#include <numeric>
#include <random>
#include <string>
#include <vector>

#include "heapsort.h"

namespace {

std::vector<int> make_input(const std::string& kind, int n) {
    std::vector<int> items(n, 7);
    if (kind == "iguales") {
        return items;
    }
    std::iota(items.begin(), items.end(), 0);
    if (kind == "desc") {
        std::reverse(items.begin(), items.end());
    } else if (kind == "azar") {
        std::mt19937 generator(13);
        std::shuffle(items.begin(), items.end(), generator);
    }
    return items;
}

}  // namespace

int main() {
    std::cout << "        n  entrada  comparaciones   /n  /(n log2 n)\n";
    for (int n : {1000, 10000, 100000, 1000000}) {
        for (const std::string kind : {"azar", "asc", "desc", "iguales"}) {
            std::vector<int> items = make_input(kind, n);
            long comparisons = 0;
            heapsort(items, [&](int a, int b) {
                comparisons++;
                return a < b;
            });
            if (!std::is_sorted(items.begin(), items.end())) {
                std::cout << "no quedo ordenado\n";
                return 1;
            }
            std::cout << std::setw(9) << n << std::setw(9) << kind << std::setw(15) << comparisons
                      << std::fixed << std::setprecision(2) << std::setw(7) << double(comparisons) / n
                      << std::setw(13) << double(comparisons) / (n * std::log2(n)) << "\n";
        }
    }
    return 0;
}

// Heapsort paso a paso, y un caso que muestra que no es estable.
#include <cstddef>
#include <iostream>
#include <string>
#include <utility>
#include <vector>

#include "heapsort.h"

namespace {

using Item = std::pair<int, char>;

void print_range(const std::vector<int>& items, std::size_t end) {
    std::cout << "[";
    for (std::size_t i = 0; i < items.size(); i++) {
        if (i == end) {
            std::cout << " | ";
        } else if (i > 0) {
            std::cout << " ";
        }
        std::cout << items[i];
    }
    if (end == items.size()) {
        std::cout << " |";
    }
    std::cout << "]\n";
}

std::string text(const std::vector<Item>& items) {
    std::string out;
    for (const Item& item : items) {
        out += std::to_string(item.first) + std::string(1, item.second) + " ";
    }
    return out;
}

}  // namespace

int main() {
    auto ascending = [](int a, int b) { return a < b; };
    std::vector<int> items = {4, 1, 7, 3, 9, 2};
    std::cout << "entrada:   ";
    print_range(items, items.size());
    build_max_heap(items, ascending);
    std::cout << "heap:      ";
    print_range(items, items.size());
    for (std::size_t end = items.size(); end > 1; end--) {
        std::swap(items[0], items[end - 1]);
        sift_down_max(items, 0, end - 1, ascending);
        std::cout << "saca " << items[end - 1] << ":    ";
        print_range(items, end - 1);
    }

    // Tres claves: los dos 2 salen en el orden contrario al de entrada.
    std::vector<Item> pairs = {{2, 'a'}, {2, 'b'}, {1, 'c'}};
    std::cout << "\nentrada: " << text(pairs) << "\n";
    heapsort(pairs, [](const Item& a, const Item& b) { return a.first < b.first; });
    std::cout << "salida:  " << text(pairs) << "\n";
    return 0;
}

// Mide heapsort frente a las ordenaciones de la biblioteca. Compilar con -O2 y sin sanitizers.
// Los tiempos dependen de la máquina.
#include <algorithm>
#include <functional>
#include <iomanip>
#include <iostream>
#include <numeric>
#include <random>
#include <vector>

#include "bench.h"
#include "heapsort.h"

namespace {

template <typename Sorter>
double time_sort(const std::vector<int>& input, Sorter sorter) {
    return median_seconds(5, [&] {
        std::vector<int> items = input;
        sorter(items);
        keep(items[items.size() / 2]);
    });
}

}  // namespace

int main() {
    std::cout << "        n   heapsort  std::sort  stable_sort  heap/sort\n";
    for (int n : {100000, 200000, 400000, 800000, 1600000, 3200000}) {
        std::vector<int> input(n);
        std::iota(input.begin(), input.end(), 0);
        std::mt19937 generator(13);
        std::shuffle(input.begin(), input.end(), generator);
        double heap = time_sort(input, [](std::vector<int>& items) { heapsort(items, std::less<int>()); });
        double quick = time_sort(input, [](std::vector<int>& items) { std::sort(items.begin(), items.end()); });
        double stable =
            time_sort(input, [](std::vector<int>& items) { std::stable_sort(items.begin(), items.end()); });
        std::cout << std::fixed << std::setprecision(4) << std::setw(9) << n << std::setw(11) << heap
                  << std::setw(11) << quick << std::setw(13) << stable << std::setprecision(2)
                  << std::setw(11) << heap / quick << "\n";
    }
    return 0;
}

// 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

// Huffman sobre una tabla pequeña. Cada árbol se guarda como su lista de códigos: al unir dos árboles,
// los códigos del primero ganan un 0 adelante y los del segundo un 1.
#include <cstddef>
#include <cstdint>
#include <iostream>
#include <queue>
#include <string>
#include <utility>
#include <vector>

namespace {

struct Symbol {
    char letter;
    long frequency;
};

struct Partial {
    long weight;
    int order;  // desempata: primero el creado antes
    std::vector<std::pair<char, std::string>> codes;
    std::string name;
};

struct Heavier {
    bool operator()(const Partial& a, const Partial& b) const {
        if (a.weight != b.weight) {
            return a.weight > b.weight;
        }
        return a.order > b.order;
    }
};

void run(const std::vector<Symbol>& symbols) {
    std::priority_queue<Partial, std::vector<Partial>, Heavier> heap;
    int order = 0;
    long total_symbols = 0;
    for (const Symbol& symbol : symbols) {
        heap.push({symbol.frequency, order++, {{symbol.letter, ""}}, std::string(1, symbol.letter)});
        total_symbols += symbol.frequency;
    }
    long merged_total = 0;
    while (heap.size() > 1) {
        Partial first = heap.top();
        heap.pop();
        Partial second = heap.top();
        heap.pop();
        std::cout << "une " << first.name << ":" << first.weight << " con " << second.name << ":" << second.weight
                  << " -> " << first.weight + second.weight << "\n";
        Partial joined{first.weight + second.weight, order++, {}, "(" + first.name + second.name + ")"};
        for (auto& [letter, code] : first.codes) {
            joined.codes.push_back({letter, "0" + code});
        }
        for (auto& [letter, code] : second.codes) {
            joined.codes.push_back({letter, "1" + code});
        }
        merged_total += joined.weight;
        heap.push(joined);
    }
    long bits = 0;
    const Partial& root = heap.top();
    for (const Symbol& symbol : symbols) {
        for (const auto& [letter, code] : root.codes) {
            if (letter == symbol.letter) {
                std::cout << symbol.letter << " (" << symbol.frequency << "): " << code << "\n";
                bits += symbol.frequency * static_cast<long>(code.size());
            }
        }
    }
    std::size_t fixed_width = 0;
    while ((std::size_t{1} << fixed_width) < symbols.size()) {
        fixed_width++;
    }
    std::cout << "bits: " << bits << ", suma de los pesos unidos: " << merged_total
              << ", con codigo fijo de " << fixed_width << " bits: " << total_symbols * static_cast<long>(fixed_width)
              << "\n";
}

}  // namespace

int main() {
    run({{'a', 5}, {'b', 2}, {'c', 1}, {'d', 1}});
    std::cout << "\n";
    run({{'a', 45}, {'b', 13}, {'c', 12}, {'d', 16}, {'e', 9}, {'f', 5}});
    std::cout << "\n";
    run({{'a', 1}, {'b', 1}, {'c', 1}, {'d', 1}});
    return 0;
}

// Min-heap de enteros sobre un arreglo. Es el heap de la clase: cuenta sus comparaciones.
#ifndef INT_HEAP_H
#define INT_HEAP_H

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

// Invariante: para todo i > 0, items_[(i - 1) / 2] <= items_[i].
// El árbol es completo porque el arreglo no tiene huecos: el nivel de abajo se llena de izquierda
// a derecha, y no hay punteros que guardar.
class IntHeap {
public:
    void push(int value) {
        items_.push_back(value);
        sift_up(items_.size() - 1);
    }

    // Requiere que no esté vacío.
    void pop() {
        assert(!items_.empty());
        items_[0] = items_.back();
        items_.pop_back();
        if (!items_.empty()) {
            sift_down(0);
        }
    }

    // Requiere que no esté vacío.
    int top() const {
        assert(!items_.empty());
        return items_[0];
    }

    bool empty() const { return items_.empty(); }
    std::size_t size() const { return items_.size(); }
    const std::vector<int>& items() const { return items_; }
    long comparisons() const { return comparisons_; }

    void check_invariants() const {
        for (std::size_t i = 1; i < items_.size(); i++) {
            assert(items_[(i - 1) / 2] <= items_[i]);
        }
    }

private:
    // Sube el elemento de i mientras sea menor que su padre.
    void sift_up(std::size_t i) {
        while (i > 0) {
            std::size_t parent = (i - 1) / 2;
            comparisons_++;
            if (items_[parent] <= items_[i]) {
                return;
            }
            std::swap(items_[parent], items_[i]);
            i = parent;
        }
    }

    // Baja el elemento de i mientras algún hijo sea menor. Se cambia con el menor de los dos.
    void sift_down(std::size_t i) {
        while (true) {
            std::size_t left = 2 * i + 1;
            std::size_t right = 2 * i + 2;
            std::size_t smallest = i;
            if (left < items_.size()) {
                comparisons_++;
                if (items_[left] < items_[smallest]) {
                    smallest = left;
                }
            }
            if (right < items_.size()) {
                comparisons_++;
                if (items_[right] < items_[smallest]) {
                    smallest = right;
                }
            }
            if (smallest == i) {
                return;
            }
            std::swap(items_[i], items_[smallest]);
            i = smallest;
        }
    }

    std::vector<int> items_;
    long comparisons_ = 0;
};

#endif

// std::priority_queue y los algoritmos de heap: el convenio de la biblioteca, y sus cotas contadas.
#include <algorithm>
#include <cmath>
#include <cstddef>
#include <functional>
#include <iostream>
#include <queue>
#include <random>
#include <vector>

namespace {

template <typename Queue>
void drain(const char* label, Queue queue) {
    std::cout << label;
    while (!queue.empty()) {
        std::cout << " " << queue.top();
        queue.pop();
    }
    std::cout << "\n";
}

}  // namespace

int main() {
    std::vector<int> values = {5, 3, 8, 1, 4};

    // Por defecto usa std::less, y deja en top() al mayor.
    std::priority_queue<int> largest_first(std::less<int>(), values);
    drain("std::less:   ", largest_first);

    // Con std::greater, deja en top() al menor.
    std::priority_queue<int, std::vector<int>, std::greater<int>> smallest_first(std::greater<int>(), values);
    drain("std::greater:", smallest_first);

    // Se cuentan las comparaciones de los algoritmos sobre un arreglo.
    const int n = 100000;
    std::vector<int> items(n);
    std::mt19937 generator(13);
    for (int& item : items) {
        item = static_cast<int>(generator() >> 8);
    }
    long count = 0;
    auto counted = [&count](int a, int b) {
        count++;
        return a < b;
    };
    std::make_heap(items.begin(), items.end(), counted);
    std::cout << "make_heap: " << count << " comparaciones, cota 3n = " << 3 * n << "\n";

    int log_n = static_cast<int>(std::log2(n));
    int twice_log_n = static_cast<int>(2 * std::log2(n));
    long worst_pop = 0;
    long worst_push = 0;
    std::vector<int> heap = items;
    for (int i = 0; i < 1000; i++) {
        count = 0;
        std::pop_heap(heap.begin(), heap.end(), counted);
        worst_pop = std::max(worst_pop, count);
        // Un valor mayor que todos los demás sube hasta la raíz: el peor caso de push_heap.
        heap.back() = (1 << 24) + i;
        count = 0;
        std::push_heap(heap.begin(), heap.end(), counted);
        worst_push = std::max(worst_push, count);
    }
    std::cout << "pop_heap, peor de 1000: " << worst_pop << ", cota 2 log2 n = " << twice_log_n << "\n";
    std::cout << "push_heap, peor de 1000: " << worst_push << ", cota log2 n = " << log_n << "\n";
    return 0;
}

// Los k mayores de n números: heap de tamaño k frente a ordenar todo.
// Cuenta comparaciones y mide tiempos, con -O2 y sin sanitizers. Los tiempos dependen de la máquina.
#include <algorithm>
#include <cstddef>
#include <functional>
#include <iomanip>
#include <iostream>
#include <queue>
#include <random>
#include <vector>

#include "bench.h"

namespace {

// Un min-heap de tamaño k: en la raíz está el peor de los k mejores hasta ahora.
template <typename Greater>
std::vector<int> k_largest(const std::vector<int>& items, std::size_t k, Greater greater) {
    std::priority_queue<int, std::vector<int>, Greater> heap(greater);
    for (int item : items) {
        if (heap.size() < k) {
            heap.push(item);
        } else if (k > 0 && greater(item, heap.top())) {
            heap.pop();
            heap.push(item);
        }
    }
    std::vector<int> result;
    while (!heap.empty()) {
        result.push_back(heap.top());
        heap.pop();
    }
    std::reverse(result.begin(), result.end());
    return result;
}

template <typename Greater>
std::vector<int> by_sorting(std::vector<int> items, std::size_t k, Greater greater) {
    std::sort(items.begin(), items.end(), greater);
    items.resize(std::min(k, items.size()));
    return items;
}

}  // namespace

int main() {
    const std::size_t n = 2000000;
    std::vector<int> items(n);
    std::mt19937 generator(13);
    for (int& item : items) {
        item = static_cast<int>(generator() >> 1);
    }

    std::cout << "n = " << n << "\n";
    std::cout << "       k  comp. heap  comp. sort  t. heap  t. sort\n";
    for (std::size_t k : {std::size_t{10}, std::size_t{1000}, std::size_t{100000}, n}) {
        long heap_count = 0;
        long sort_count = 0;
        auto count_heap = [&](int a, int b) {
            heap_count++;
            return a > b;
        };
        auto count_sort = [&](int a, int b) {
            sort_count++;
            return a > b;
        };
        std::vector<int> from_heap = k_largest(items, k, count_heap);
        std::vector<int> from_sort = by_sorting(items, k, count_sort);
        if (from_heap != from_sort) {
            std::cout << "no coinciden\n";
            return 1;
        }
        double heap_time = median_seconds(3, [&] { keep(k_largest(items, k, std::greater<int>()).size()); });
        double sort_time = median_seconds(3, [&] { keep(by_sorting(items, k, std::greater<int>()).size()); });
        std::cout << std::setw(8) << k << std::setw(12) << heap_count << std::setw(12) << sort_count
                  << std::fixed << std::setprecision(4) << std::setw(9) << heap_time << std::setw(9)
                  << sort_time << "\n";
    }
    return 0;
}

// ¿Dónde puede estar el máximo de un min-heap? Revisa todas las permutaciones de 7 claves.
#include <algorithm>
#include <array>
#include <cstddef>
#include <iostream>
#include <numeric>
#include <vector>

namespace {

bool is_min_heap(const std::vector<int>& items) {
    for (std::size_t i = 1; i < items.size(); i++) {
        if (items[(i - 1) / 2] > items[i]) {
            return false;
        }
    }
    return true;
}

}  // namespace

int main() {
    std::vector<int> items(7);
    std::iota(items.begin(), items.end(), 1);
    std::array<int, 7> least_at{};
    std::array<int, 7> greatest_at{};
    int total = 0;
    int heaps = 0;
    do {
        total++;
        if (is_min_heap(items)) {
            heaps++;
            least_at[std::min_element(items.begin(), items.end()) - items.begin()]++;
            greatest_at[std::max_element(items.begin(), items.end()) - items.begin()]++;
        }
    } while (std::next_permutation(items.begin(), items.end()));

    std::cout << "permutaciones: " << total << ", son heaps: " << heaps << "\n";
    std::cout << "indice  minimo  maximo\n";
    for (std::size_t i = 0; i < items.size(); i++) {
        std::cout << "     " << i << "  " << least_at[i] << "      " << greatest_at[i] << "\n";
    }
    // Con claves repetidas, un nodo interno puede valer lo mismo que el máximo.
    std::vector<int> repeated = {1, 2, 2, 2};
    std::cout << "[1 2 2 2] es heap: " << (is_min_heap(repeated) ? "si" : "no")
              << ", y el indice 1 vale el maximo y tiene un hijo\n";
    return 0;
}

// Error a propósito: buscar en un heap como si fuera un árbol de búsqueda.
#include <cstddef>
#include <iostream>
#include <vector>

namespace {

// Baja a la izquierda si la clave es menor, y a la derecha si es mayor. En un heap, eso no sirve.
bool looks_like_bst_search(const std::vector<int>& heap, int key) {
    std::size_t i = 0;
    while (i < heap.size()) {
        if (heap[i] == key) {
            return true;
        }
        i = key < heap[i] ? 2 * i + 1 : 2 * i + 2;
    }
    return false;
}

}  // namespace

int main() {
    std::vector<int> heap = {1, 3, 8, 5, 4};
    for (int key : heap) {
        std::cout << "busca " << key << ": " << (looks_like_bst_search(heap, key) ? "esta" : "NO ESTA") << "\n";
    }
    return 0;
}

// Error a propósito: al bajar, cambiar siempre con el hijo izquierdo, sin mirar cuál es el menor.
#include <cstddef>
#include <iostream>
#include <utility>
#include <vector>

namespace {

void sift_down_wrong(std::vector<int>& heap, std::size_t i) {
    while (2 * i + 1 < heap.size() && heap[2 * i + 1] < heap[i]) {
        std::swap(heap[i], heap[2 * i + 1]);
        i = 2 * i + 1;
    }
}

bool is_min_heap(const std::vector<int>& heap) {
    for (std::size_t i = 1; i < heap.size(); i++) {
        if (heap[(i - 1) / 2] > heap[i]) {
            return false;
        }
    }
    return true;
}

}  // namespace

int main() {
    std::vector<int> heap = {1, 4, 2, 5, 6, 3};
    std::cout << "antes de sacar: es heap: " << (is_min_heap(heap) ? "si" : "no") << "\n";
    heap[0] = heap.back();
    heap.pop_back();
    sift_down_wrong(heap, 0);
    std::cout << "arreglo:";
    for (int item : heap) {
        std::cout << " " << item;
    }
    std::cout << "\nraiz: " << heap[0] << ", es heap: " << (is_min_heap(heap) ? "si" : "no") << "\n";
    return 0;
}

// Error a propósito: un decodificador que lee un bit antes de mirar si ya está en una hoja.
// Con un árbol de una sola hoja, que es el de un archivo con un solo símbolo, baja a un hijo que no existe.
#include <iostream>
#include <vector>

namespace {

struct Node {
    int symbol;
    int left;
    int right;
};

char decode_one(const std::vector<Node>& nodes, int root, bool bit) {
    int node = root;
    do {
        node = bit ? nodes[node].right : nodes[node].left;
    } while (nodes[node].left >= 0);
    return static_cast<char>(nodes[node].symbol);
}

}  // namespace

int main() {
    std::vector<Node> nodes = {{'a', -1, -1}};
    std::cout << decode_one(nodes, 0, false) << "\n";
    return 0;
}

// Error a propósito: descomprimir hasta que se acaben los bits, sin mirar el tamaño original.
#include <iostream>
#include <string>

namespace {

// a = 1, b = 0: un árbol con dos hojas. Decodifica cada bit de una cadena.
std::string decode(const std::string& bits) {
    std::string out;
    for (char bit : bits) {
        out += bit == '1' ? 'a' : 'b';
    }
    return out;
}

}  // namespace

int main() {
    // El texto "aab" da los bits 110. El último byte se rellena con ceros hasta 8 bits.
    std::string bits = "110";
    std::string byte = bits + std::string(8 - bits.size(), '0');
    std::cout << "original: aab\n";
    std::cout << "bits en el archivo: " << byte << "\n";
    std::cout << "sin mirar el tamano: " << decode(byte) << "\n";
    std::cout << "con tamano 3: " << decode(byte.substr(0, 3)) << "\n";
    return 0;
}

// Error a propósito: usar un char como índice de la tabla de frecuencias.
// Se compila con -fsigned-char para que pase lo mismo en toda arquitectura.
#include <array>
#include <cstdio>
#include <string>

int main() {
    std::string text = "ñ";  // en UTF-8 son dos bytes: 0xC3 y 0xB1
    std::array<long, 256> counts{};
    for (char c : text) {
        counts.data()[c]++;
    }
    std::printf("contó %ld\n", counts[0xC3]);
    return 0;
}