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