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