Priority Queue with a Binary Heap Structure

binaryheappq.cpp

#include <iostream>
#include <memory>

template<class T>
class LessThan{
public:
    inline static bool apply(T const& a, T const& b){
        return a < b;
    }
};

template<class T>
class LessThan<T*>{
public:
    inline static bool apply(T const* a, T const* b){
        return *a < *b;
    }
};

template<class T>
class LessThan<std::shared_ptr<T>>{
public:
    inline static bool apply(std::shared_ptr<T> const& a, std::shared_ptr<T> const& b){
        return *a < *b;
    }
};

template<class T, int N, class Less = LessThan<T>>
class PriorityQueue{
public:
    
    PriorityQueue() : used_(0), elements_(new T[LAST]){

    }
    
    PriorityQueue(PriorityQueue const& other) : elements_(new T[other.capacity()]), used_(other.used_){
        std::copy(other.elements_, other.elements_ + other.capacity(), elements_);
    }
    
    PriorityQueue& operator = (PriorityQueue const& other){
        T* temp = new T[other.capacity()];
        std::copy(other.elements_, other.elements_ + other.capacity(), temp);
        delete elements_;
        elements_ = temp;
        used_ = other.used_;
    }
    
    inline T& max(){
        return elements_[FIRST];
    }
    
    inline T const & max() const{
        return elements_[FIRST];
    }
    
    void insert(T const& item){
        elements_[++used_] = item;
        swim(used_);
    }
    
    inline bool full() const{
        return used_ == N;
    }
    
    void deleteMax(){
        using std::swap;
        swap(elements_[used_],elements_[FIRST]);
        sink(FIRST);
        elements_[used_--] = T();
    }
    
    inline int capacity() const{
        return N;
    }
    
    ~PriorityQueue(){
        delete elements_;
    }
    
private:
    
    void swim(size_t position){
        while(position > 1 && Less::apply(elements_[ position / 2], elements_[position]))
        {
            using std::swap;
            swap(elements_[ position / 2], elements_[position]);
            position /= 2;
        }
    }

    void sink(int position){
        while(position * 2 <= used_){
            int first = position * 2;
            int second = first + 1;
            if(first > used_) break;
            
            bool second_larger = Less::apply(elements_[first], elements_[second]);
            int greater_child = second_larger ? second : first;
            
            bool parent_smaller = Less::apply(elements_[position], elements_[greater_child]);
            if(!parent_smaller)
                break;
            
            std::swap(elements_[greater_child], elements_[position]);
            position = greater_child;
        }
    }
    
    inline int current_position() const{
        return used_ + 1;
    }
    
    static const int MAX = N + 1;
    static const int FIRST = 1;
    static const int LAST = N;
    T* elements_;
    size_t used_;
};

int main(int argc, const char * argv[])
{

    PriorityQueue<int, 8> p;
    p.insert(1);
    p.insert(2);
    p.insert(3);
    p.insert(4);
    p.insert(5);
    p.insert(6);
    
    std::cout << "Max: " << p.max() << std::endl;
    
    p.deleteMax();
    
    std::cout << "Max: " << p.max() << std::endl;
    
    return 0;
}