#include <iostream>
#include <string>
#include <sstream>
#include <functional>
#include <cmath>
#include <time.h>
#include <cstdlib>
//dolaczyc tablice dynamiczna

using namespace std;

class Person {
public:
    string name;
    int age;

    Person(int age, string name) {
        this->name = name;
        this->age = age;
    }

    Person() {}

};

template<class T>
class DynamicArray {
    int maxSize = 1;
    int extendRatio = 2;
    T *array;
public:
    int size = 0;

    DynamicArray() {
        array = new T[maxSize];
    }


    void add(T data) {
        if (maxSize > size) {
            array[size] = data;
            size++;
        } else {
            maxSize = extendRatio * size;
            T *newArray = new T[maxSize];
            for (int i = 0; i < size; i++) {
                newArray[i] = array[i];
            }
            newArray[size] = data;
            size++;
            delete[] array;
            array = newArray;
        }
    }

    T get(int index) {
        if (index < 0) {
            throw 0;
        }
        if (index >= size) {
            throw 1;
        }
        return array[index];
    }

    bool exist(int index) {
        return (index < size && index > 0);
    }

    void set(int index, T data) {
        if (index < 0) {
            throw 2;
        }
        if (index >= size) {
            throw 3;
        }
        array[index] = data;
    }

    void clear() {
        delete[] array;
        size = 0;
    }

    // display only n first elements
    string toString(function<string(T)> f) {
        ostringstream result;
        result << "Size = " << size << endl << "Max size = " << maxSize << endl;
        for (int i = 0; i < size; i++) {
            result << i << ": " << f(array[i]) << endl;
        }
        return result.str();
    }

    string toString(function<string(T)> f, int n) {
        ostringstream result;
        result << "Size = " << size << endl << "Max size = " << maxSize << endl;
        for (int i = 0; i < n; i++) {
            result << i << ": " << f(array[i]) << endl;
        }
        return result.str();
    }

};

template<class T>
class Node {
public:
    T value;
    Node<T> *parent = NULL;
    Node<T> *leftKid = NULL;
    Node<T> *rightKid = NULL;

};

template<class T>
class BinaryHeap {
    DynamicArray<T> *dynamicArray;
public:

    BinaryHeap() {
        dynamicArray = new DynamicArray<T>();
    }

    ~BinaryHeap() {
        delete dynamicArray;
    }


    void add(T data, function<bool(T, T)> compare) {
        dynamicArray->add(data);
        int dataIndex = dynamicArray->size - 1;
        int parentIndex = ((dataIndex - 1) / 2);

        int x = compare(data, dynamicArray->get(parentIndex));

        while (x == -1) {
            swap(dataIndex, parentIndex);

            dataIndex = parentIndex;
            parentIndex = ((dataIndex - 1) / 2);
            x = compare(data, dynamicArray->get(parentIndex));
        }
    }

    void poll(function<bool(T, T)> compareKids) {
        int dataIndex = 0;
        int kidLeftIndex = 2 * dataIndex + 1;
        int kidRightIndex = 2 * dataIndex + 2;

        if (dynamicArray->size == 0) {
            return;
        }
        dynamicArray->set(0, dynamicArray->get(dynamicArray->size - 1));

        bool leftGreater =
                dynamicArray->exist(kidLeftIndex) && dynamicArray->get(kidLeftIndex) > dynamicArray->get(dataIndex);
        bool rightGreater =
                dynamicArray->exist(kidRightIndex) && dynamicArray->get(kidRightIndex) > dynamicArray->get(dataIndex);

        while (leftGreater || rightGreater) {

            int x = compareKids(dynamicArray->get(kidLeftIndex), dynamicArray->get(kidRightIndex));
            if (x == 1) {
                swap(dataIndex, kidLeftIndex);
                dataIndex = kidLeftIndex;
            } else {
                swap(dataIndex, kidRightIndex);
                dataIndex = kidRightIndex;
            }

            kidLeftIndex = 2 * dataIndex + 1;
            kidRightIndex = 2 * dataIndex + 2;

            leftGreater =
                    dynamicArray->exist(kidLeftIndex) && dynamicArray->get(kidLeftIndex) > dynamicArray->get(dataIndex);
            rightGreater = dynamicArray->exist(kidRightIndex) &&
                           dynamicArray->get(kidRightIndex) > dynamicArray->get(dataIndex);
        }
        dynamicArray->size--;
    }

    string toString(function<string(T)> f) {
        return dynamicArray->toString(f);
    }

private:
    void swap(int index1, int index2) {
        T tmp = dynamicArray->get(index2);
        dynamicArray->set(index2, dynamicArray->get(index1));
        dynamicArray->set(index1, tmp);
    }

    void heapUp() {

    }
};


int compare(Person newPerson, Person elem) {
    if (newPerson.age == elem.age) {
        return 0;
    } else if (newPerson.age < elem.age) {
        return -1;
    } else {
        return 1;
    }
}

int compareInt(int newInt, int x) {
    if (newInt == x) {
        return 0;
    } else if (newInt < x) {
        return -1;
    } else {
        return 1;
    }
}

string intToString(int n) {
    ostringstream ss;
    ss << n;
    return ss.str();
}

int main() {
    try {
        BinaryHeap<int> bh;
        bh.add(6, compareInt);
        bh.add(5, compareInt);
        bh.add(4, compareInt);
        bh.add(3, compareInt);
        bh.add(2, compareInt);
        bh.add(1, compareInt);

        bh.poll(compareInt);
        cout << bh.toString(intToString);

        cout << "Xd";
    } catch (int e) {
        cout << e;
    }
}