heap.cpp

#include <algorithm>
#include <functional>
#include <iostream>
#include <memory>
#include <vector>

#if 0
template <typename F>
void myfunc(int a, int b, F f)
{
    if (f(a, b))
        std::cout << a << std::endl;
    else
        std::cout << b << std::endl;
}
#endif

template <typename F, size_t K, size_t v>
class Heap
{
public:
    Heap() = delete;

    Heap(F f_) : f(f_), data_t(std::make_shared<std::vector<size_t>>(K, v)) { std::make_heap(data_t->begin(), data_t->end(), f); };

    void insertAndReplace(size_t new_v)
    {
        data_t->push_back(new_v);
        std::push_heap(data_t->begin(), data_t->end(), f);
        std::pop_heap(data_t->begin(), data_t->end(), f);
        data_t->pop_back();
    }

    void dumpValue()
    {
        for (auto i : *data_t)
            std::cout << i << std::endl;
    }

private:
    F f;
    std::shared_ptr<std::vector<size_t>> data_t;
};

using Less = std::less<size_t>;
using Greater = std::greater<size_t>;
using MaxHeap = Heap<std::less<size_t>, 7, -1ULL>;
using MinHeap = Heap<std::greater<size_t>, 7, 0>;

int main()
{
    // myfunc(1, 4, std::greater<int>{});
    MaxHeap max_heap(Less{});
    max_heap.insertAndReplace(10);
    std::cout << "after insert 10\n";
    max_heap.dumpValue();
    max_heap.insertAndReplace(12332);
    std::cout << "after insert 12332\n";
    max_heap.dumpValue();
    max_heap.insertAndReplace(10);
    std::cout << "after insert 10\n";
    max_heap.dumpValue();

    MinHeap min_heap(Greater{});
    min_heap.insertAndReplace(10);
    std::cout << "after insert 10\n";
    min_heap.dumpValue();
    min_heap.insertAndReplace(12332);
    std::cout << "after insert 12332\n";
    min_heap.dumpValue();
    min_heap.insertAndReplace(10);
    std::cout << "after insert 10\n";
    min_heap.dumpValue();
}