[STL] priority_queue

이번에 시험보면서 구현해 보는데 애를 먹어서 다시 한번 구현해 보게 되었다. 

이게 꽉차면 동적으로 재할당 되면서 늘어나게 하고 싶어서 벡터를 재할당 하듯이 구현해 봤다.

이러면 매번 재사용 할 때 메모리를 덜 잡아먹지 않을까? 하는 바람으로..

template <typename T>
void _swap(T& e1, T& e2){
    T tmp = e1; e1 = e2; e2 = tmp;
}
 
template <class T>
class _priority_queue{
private:
    T* pq;
    int _size, cap;
public:
    _priority_queue<T>():_size(0), cap(2){
        pq = new T[cap];
    };
    ~_priority_queue<T>(){
        delete[] pq;
    }
    void resize(int ncap){
        cap = ncap;
        T* tmp = new T[cap];
        for(int i = 0; i <= _size; i++)
            tmp[i] = pq[i];
        delete[] pq;
        pq = tmp;
    }
    int full(){return _size == cap - 1;}
    int empty(){return _size == 0;}
    T top(){return pq[1];}
    void push(T e){
        if(full()) resize(cap * 2);
        pq[++_size] = e;
        int root = _size;
        while(root > 1){
            if(pq[root] < pq[root / 2]) break;
            _swap(pq[root], pq[root / 2]);
            root /= 2;
        }
    }
    void pop(){
        if(empty()) return;
        pq[1] = pq[_size--];
        int root = 1;
        while (root<_size){
            int nxt = root;
            if (root * 2 <= _size && pq[root * 2]>pq[nxt]) nxt = root * 2;
            if (root * 2 + 1 <= _size && pq[root * 2 + 1]>pq[nxt]) nxt = root * 2 + 1;
            if (nxt == root)break;
            _swap(pq[root], pq[nxt]);
            root = nxt;
        }
    }
    void clear(){
        delete[] pq;
        _size = 0, cap = 2;
        pq = new T[cap];
    }
};