Max heap

maxheap.cpp

#include <iostream>
#include <map>
#include <utility>
#include <queue>
#include <algorithm>
using namespace std;

template<class T>
class MaxHeap {
public:
    MaxHeap()=default;
    MaxHeap(size_t s){a.reserve(s);}
    void push(T const&);
    int size() const;
    T pop();
    void heapifyUp();
    void heapifyDown(int);
    T top() const { return a[0]; }
    int Left(int i) const { return i*2+1; }
    int Right(int i) const { return i*2+2; }
    int Parent(int i) const { return (i - 1)/2; }
    bool empty()const{return a.empty();}
private:
    vector<T> a; // heap structure
};

template<class T>
void MaxHeap<T>::heapifyUp() {
    int smallest = size()-1;
    while (Parent(smallest) >= 0 && a[smallest] > a[Parent(smallest)]) {
        swap(a[smallest], a[Parent(smallest)]);
        smallest = Parent(smallest);
    }
}

template<class T>
void MaxHeap<T>::heapifyDown(int i) {
    int largest = i;
    int left    = Left(i);
    int right   = Right(i);

    if( left < size() && a[largest] < a[ left ])
        largest = left;
    if( right < size()  && a[largest] < a[right])
        largest = right;
    if( largest != i ){
        swap( a[i], a[largest] );
        heapifyDown( largest );
    }
}

template<class T>
void MaxHeap<T>::push(T const& n) {
    a.push_back(n);
    heapifyUp();
}

template<class T>
T MaxHeap<T>::pop() {
    T old = a[0];
    swap(a[0], a.back());
    a.pop_back();
    heapifyDown(0);
    return old;
}

template<class T>
int MaxHeap<T>::size() const {
    return a.size();
}