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