// Cola de prioridad sobre un heap binario guardado en un arreglo.
// Completen cada método marcado con not_implemented. La semana 15 usará esta clase en Dijkstra:
// no cambien estas firmas.
#ifndef MIN_HEAP_H
#define MIN_HEAP_H

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

#include "not_implemented.h"

// less(a, b) dice si a tiene que estar más cerca de la raíz que b. Debe ser un orden estricto.
// Invariante: para todo i > 0, el hijo items_[i] no es menor que su padre items_[(i - 1) / 2].
// El árbol es completo porque el arreglo no tiene huecos.
// Ownership: el arreglo es un std::vector, así que copiar, mover y destruir ya funcionan.
// La referencia de top() vale hasta el próximo push o pop.
template <typename T, typename Less = std::less<T>>
class MinHeap {
    friend struct MinHeapTestAccess;

public:
    MinHeap() = default;

    explicit MinHeap(Less less) : less_(std::move(less)) {}

    // Paso 1: construye de abajo hacia arriba, desde el último padre hasta la raíz. Cuidado con los
    // tamaños 0 y 1: size_t no tiene negativos. Una prueba cuenta las comparaciones.
    explicit MinHeap(std::vector<T> items, Less less = Less()) : items_(std::move(items)), less_(std::move(less)) {
        not_implemented("MinHeap(items)");
    }

    // Paso 1: agrega al final y sube. Muevan el valor: una prueba cuenta las copias.
    void push(T value) {
        (void)value;
        not_implemented("push");
    }

    // Paso 1: la última hoja pasa a la raíz, y baja. Requiere que no esté vacío.
    void pop() {
        assert(!items_.empty());
        not_implemented("pop");
    }

    // Requiere que no esté vacío.
    const T& top() const {
        assert(!items_.empty());
        return items_.front();
    }

    bool empty() const { return items_.empty(); }
    std::size_t size() const { return items_.size(); }

    // Paso 1: detiene el programa, con assert, si algún hijo es menor que su padre.
    // Usen solo less_: T no tiene por qué tener operator<.
    void check_invariants() const { not_implemented("check_invariants"); }

private:
    // Sugerimos dos funciones privadas, sift_up y sift_down. Usen std::swap o std::move, sin copiar T.

    std::vector<T> items_;
    Less less_{};
};

#endif