// 手写小根堆
template<typename T>
class lyhMinHeap{
public:
    lyhMinHeap(int size = 10){
        maxSize = size;
        heap = new T[maxSize];
        curSize = 0;
    }

    bool Insert(const T& x){// 插入新的元素。若输入8，因为8是个右值，形参需要加const 修饰
        if(curSize >= maxSize){
            cout << "满了" << endl;
            return false;
        }
        heap[curSize] = x;
        siftUp(curSize);
        curSize++;
        return true;
    }

    void output(){
        for(int i = 0; i < curSize; i++)
            cout << heap[i] << ", ";
        cout << endl;
    }

    bool RemoveMin(T& x){ // 弹出堆顶，即最小元素
        if(curSize <= 0){
            cout << "empty!!" << endl;
            return false;
        }
        x = heap[0];
        heap[0] = heap[curSize-1];
        curSize--;
        siftDown(0,curSize-1);
        return true;
    }

private:
    T* heap; // 数组模拟堆
    int curSize; // 当前堆中元素数量
    int maxSize; // 堆最大可容纳元素数量

    void siftUp(int start){ // 辅助上移
        int cur = start;
        int parent = (cur-1)/2;
        T& temp = heap[cur];
        while(parent >= 0){
            if(heap[parent] > temp){
                heap[cur] = heap[parent];
                cur = parent;
                parent = (cur -1)/2;
            }else
                break;
        }
        heap[cur] = temp;
    }

    void siftDown(int start, int end){ // 辅助下移
        int cur = start;
        int lc = 2*cur +1;
        T& temp = heap[cur];
        while(lc <= end){
            if(lc+1 <= end && heap[lc+1] < heap[lc]) lc++;
            if(heap[lc] < temp){
                heap[cur] = heap[lc];
                cur = lc;
                lc = 2*cur +1;
            }else  
                break;
        }
        heap[cur] = temp;
    }
};