Binary Heap implemented using C++ STL algorithms for heaps

binary_heap.hpp

#ifndef BINARY_HEAP_HPP
#define BINARY_HEAP_HPP

#include <algorithm>
#include <functional>
#include <initializer_list>
#include <iostream>
#include <stack>
#include <type_traits>
#include <vector>
#include <utility>


namespace binary_heap {
    

template<typename T,
         typename Container = std::vector<T>, //STL container that supports push_back, like list or vector
         typename Comparator = std::less<T>>
class base_heap {
private:
    Container data_;

public:
    using container_type  = Container;
    using value_compare   = Comparator;
    using value_type      = typename Container::value_type;
    using size_type       = typename Container::size_type;
    using const_reference = typename Container::const_reference;
    using const_iterator  = typename Container::const_iterator;
 
    
    template<typename InputIt>
    explicit base_heap(InputIt begin, InputIt end)
        : data_(begin, end)
    {
        static_assert(std::is_same<value_type, T>::value,
                      "Type of data in Heap and Container must be the same");
        
        std::make_heap(data_.begin(), data_.end(), Comparator());
    }
    
    base_heap(const std::initializer_list<T>& lst)
        : base_heap(std::begin(lst), std::end(lst)) {}
        
    base_heap(std::initializer_list<T>&& lst)
        : data_(std::move(lst))
    {
        static_assert(std::is_same<value_type, T>::value,
                      "Type of data in Heap and Container must be the same");
        
        std::make_heap(data_.begin(), data_.end(), Comparator());
    }
    
    base_heap() // default constructs an empty heap
        : data_() {}
    
    base_heap(const base_heap&) = default;
    base_heap& operator=(const base_heap&) = default;
    base_heap(base_heap&&) = default;
    base_heap& operator=(base_heap&&) = default;
    ~base_heap() noexcept = default;
    
    bool             empty() const noexcept {return data_.empty(); }
    size_type         size() const noexcept {return data_.size();  }
    const Container   data() const noexcept {return data_;         }
    const_reference    top() const noexcept {return *data_.begin();}
    const_iterator   begin() const noexcept {return data_.begin(); }
    const_iterator     end() const noexcept {return data_.end();   }
    
    const_reference operator[](std::size_t index) const noexcept
    {
        return data_[index];
    }
    
    void pop()
    {
        std::pop_heap(data_.begin(), data_.end(), Comparator());
        data_.pop_back();
    }
    
    template<typename Data>
    typename std::enable_if<std::is_convertible<Data,T>::value,void>::type
    push(Data&& arg)
    {
        data_.push_back(std::forward<Data>(arg));
        std::push_heap(data_.begin(), data_.end(), Comparator());
    }
    
    template<typename... Args>
    void emplace(Args&&... args)
    {
        data_.emplace_back(std::forward<Args>(args)...);
        std::push_heap(data_.begin(), data_.end(), Comparator());
    }
    
    void swap(base_heap& other)
    {
        std::swap(data_, other.data_);
    }
       
    const Container sorted_array() const
    {
        Container tmp (data_); // copy
        std::sort_heap(tmp.begin(), tmp.end(), Comparator());
        return tmp;
    }
        
    bool search(const value_type& elem) const noexcept
    {
        /*
        if (index >= data_.size()) return false;
        else if (data_[index] == elem) return true;
        else {
            if (index == 0) return search(elem, 1);
            else {
                return search(elem, 2*index) ||
                       search(elem, 2*index + 1);
            }
        }*/
        
        std::stack<std::size_t> st;
        st.push(0);
        
        while (!st.empty()) {
            auto index = st.top();
            st.pop();
            
            if (data_[index] == elem) return true;
            
            if (index == 0) st.push(1);
            else {
                index *= 2;
                if (index < data_.size()) st.push(index);
                if (index+1 < data_.size()) st.push(index+1);
            }
        }
        
        return false;
    }
};

template<typename X>
using min_heap = base_heap<X, std::vector<X>, std::greater<X>>;

template<typename X>
using max_heap = base_heap<X, std::vector<X>, std::less<X>>;

} // end of namespace binary heap

#endif // BINARY_HEAP_HPP