Heap.cpp

#include <iostream>
#include <vector>
#include <functional>
using namespace std;

template <typename T, typename Compare = less<T>>
class Heap
{
private:
    vector<T> data;
    Compare comp; // comparator: less = min-heap, greater = max-heap

    void heapify_up(int idx)
    {
        while (idx > 0)
        {
            int parent = (idx - 1) / 2;
            if (comp(data[idx], data[parent]))
            {
                swap(data[idx], data[parent]);
                idx = parent;
            }
            else
                break;
        }
    }

    void heapify_down(int idx)
    {
        int n = data.size();
        while (true)
        {
            int left = 2 * idx + 1, right = 2 * idx + 2, smallest = idx;
            if (left < n && comp(data[left], data[smallest]))
                smallest = left;
            if (right < n && comp(data[right], data[smallest]))
                smallest = right;
            if (smallest != idx)
            {
                swap(data[idx], data[smallest]);
                idx = smallest;
            }
            else
                break;
        }
    }

public:
    Heap(Compare c = Compare()) : comp(c) {}

    bool empty() const { return data.empty(); }
    int size() const { return data.size(); }

    const T &top() const
    {
        if (empty())
            throw runtime_error("Heap is empty!");
        return data[0];
    }

    void push(const T &value)
    {
        data.push_back(value);
        heapify_up(data.size() - 1);
    }

    void pop()
    {
        if (empty())
            throw runtime_error("Heap is empty!");
        data[0] = data.back();
        data.pop_back();
        if (!empty())
            heapify_down(0);
    }
};