//小根堆
template<class T>
class Heap
{
public:
    typedef T DataType;

public:

    Heap() :
        data(vector<DataType>(1)) {}
    Heap(const vector<DataType>& _data)
    {
        data = vector<DataType>(1);
        for (auto i : _data)
            Insert(i);
    }
    Heap(const Heap<T>& _instance)
    {
        data.assign(_instance.data.begin(), _instance.data.end());
    }

public:
    void Insert(DataType v)
    {
        data.push_back(v);
        Up(data.size() - 1);
    }
    void Pop()
    {
        swap(data[1], data[data.size() - 1]);
        data.pop_back();
        Down(1);
    }
    DataType Top()
    {
        return data[1];
    }
    //删除编号为x的数，编号非法则不操作
    void Erase(int x)
    {
        if (x > data.size() - 1)return;
        swap(data[data.size() - 1], data[x]);
        data.pop_back();
        Down(x);
        Up(x);
    }
    //将编号为x的数的值改为d
    void Change(int x, DataType d)
    {
        if (x > data.size() - 1)return;
        data[x] = d;
        Down(x);
        Up(x);
    }
    int Size()
    {
        return data.size();
    }
public:
    DataType operator[](int k)
    {
        return data.at(k);
    }
protected:

private:
    vector<DataType> data;
private:
    //将编号为x的点向上调整
    void Up(int x)
    {
        while (x > 1 && x / 2 >= 1 && data[x] < data[x / 2])
        {
            swap(data[x / 2], data[x]);
            x /= 2;
        }
    }
    void Down(int x)
    {
        //无左右子节点
        if (2 * x > data.size() - 1)
            return;
        //无右节点
        if (2 * x + 1 > data.size() - 1)
        {
            if (data[x] > data[2 * x])
                swap(data[x], data[2 * x]);
            else return;
            Down(x * 2);
        }
        else
        {
            int Min = data[2 * x] > data[2 * x + 1] ? 2 * x + 1 : 2 * x;
            if (data[x] < data[Min])
                return;
            swap(data[x], data[Min]);
            Down(Min);
        }
    }
};