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