#include <vector>

using namespace std;

#define db(a) cout << #a << " = " << a << endl
#define db2(a, b) cout << #a << " = " << a << " " << #b << " = " << b << endl;

template<typename T> class MyHeap {
protected:
    int capacity;
    int size;
    vector<T> items;

    virtual void heapifyUp() {}
    virtual void heapifyDown() {}

    bool hasParent(int index) {
        return (index - 1) / 2 >= 0;
    }
    bool hasLeftValue(int index) {
        return 2 * index + 1 < size;
    }
    bool hasRightValue(int index) {
        return 2 * index + 2 < size;
    }
    int getParent(int index) {
        return items[(index - 1) / 2];
    }
    int getCurrent(int index) {
        return items[index];
    }
    int getParentIndex(int index) {
        return (index - 1) / 2;
    }
    void swap(int first, int last) {
        T temp = items[first];
        items[first] = items[last];
        items[last] = temp;
    }
    int getLeftValue(int index) {
        return items[2 * index + 1];
    }
    int getRightValue(int index) {
        return items[2 * index + 2];
    }
    int getLeftIndex(int index) {
        return 2 * index + 1;
    }
    int getRightIndex(int index) {
        return 2 * index + 2;
    }
public:
    MyHeap() {
        capacity = 0;
        size = 0;
    }
    virtual void saludar() = 0;
    void add(T item) {
        items.push_back(item);
        size++;
        heapifyUp();
    }
    T poll() {
        T temp = items[0];
        items[0] = items[size - 1];
        size--;
        heapifyDown();
        return temp;
    }
};

template<typename T>
class MaxHeap : public MyHeap<T> {
public:
    MaxHeap() : MyHeap<T>() { }
    void saludar() {
        cout << "implementado" << endl;
    }
    void heapifyUp() {
        int curindex = this->size - 1, parindex;
        while (this->hasParent(curindex) && this->getParent(curindex) < this->getCurrent(curindex)) {
            parindex = this->getParentIndex(curindex);
            this->swap(parindex, curindex);
            curindex = parindex;
        }
    }
    void heapifyDown() {
        int curindex = 0, maxindex;
        while(this->hasLeftValue(curindex)) {
            maxindex = this->getLeftValue(curindex) > this->getCurrent(curindex)
            ? this->getLeftIndex(curindex) : curindex;
            if (this->hasRightValue(curindex) &&
                this->getRightValue(curindex) > this->getCurrent(maxindex)) {
                maxindex = this->getRightIndex(curindex);
            }
            if (curindex != maxindex) {
                this->swap(curindex, maxindex);
                curindex = maxindex;
            }
            else break;
        }
    }
};
template<typename T>
class MinHeap : public MyHeap<T> {
public:
    MinHeap() : MyHeap<T>() { }
    void saludar() {
        cout << "implementado en minheap" << endl;
    }
    void heapifyUp() {
        int curindex = this->size - 1, parindex;
        while (this->hasParent(curindex) && this->getParent(curindex) > this->getCurrent(curindex)) {
            parindex = this->getParentIndex(curindex);
            this->swap(parindex, curindex);
            curindex = parindex;
        }
    }
    void heapifyDown() {
        int curindex = 0, minindex;
        while(this->hasLeftValue(curindex)) {
            minindex = this->getLeftValue(curindex) < this->getCurrent(curindex)
            ? this->getLeftIndex(curindex) : curindex;
            if (this->hasRightValue(curindex) &&
                this->getRightValue(curindex) < this->getCurrent(minindex)) {
                minindex = this->getRightIndex(curindex);
            }
            if (curindex != minindex) {
                this->swap(curindex, minindex);
                curindex = minindex;
            }
            else break;
        }
    }
};