CppHeap.h

Go to the documentation of this file.

 
#pragma once
 
#include <algorithm>
#include <exception>
#include <vector>
 
namespace alib {
 
template < typename T, typename Comparator = std::less < T > >
class CppHeap {
public:
    CppHeap( Comparator comparator = Comparator ( ) ) : m_comparator( comparator ) {
    }
 
    // inserts a node with new value into the heap
    void insert ( const T & value );
 
    const T & getMax ( ) const {
        return m_data.front ( );
    }
 
    T extractMax ( );
 
    void mergeWith ( CppHeap < T, Comparator > && that );
 
    size_t size ( ) const {
        return m_data.size ( );
    }
 
protected:
    Comparator m_comparator;
    std::vector < T > m_data;
};
 
 
template < typename T, typename Comparator >
void CppHeap < T, Comparator >::insert ( const T & value ) {
    m_data.push_back ( value );
    std::push_heap ( m_data.begin ( ), m_data.end ( ), m_comparator );
}
 
template < typename T, typename Comparator >
T CppHeap < T, Comparator >::extractMax ( ) {
    if ( m_data.size ( ) == 0 )
        throw std::out_of_range ( "Heap is empty." );
 
    std::pop_heap ( m_data.begin ( ), m_data.end ( ), m_comparator );
    T res = std::move ( m_data.back ( ) );
    m_data.pop_back ( );
    return res;
}
 
template < typename T, typename Comparator >
void CppHeap < T, Comparator >::mergeWith( CppHeap < T, Comparator > && that ) {
    m_data.insert ( m_data.end ( ), that.m_data.begin ( ), that.m_data.end ( ) );
    std::make_heap ( m_data.begin ( ), m_data.end ( ), m_comparator );
}
 
} /* namespace alib */