#ifndef __GBLIBCPP_QUEUE__
#define __GBLIBCPP_QUEUE__

#include <vector>
#include <functional>
#include <memory>
#include <algorithm>
#include <initializer_list>
#include <cstddef>

namespace std {

template <typename T,
    typename Container = std::vector<T>,
    typename Compare = std::less<typename Container::value_type>>
class priority_queue {
public:
    using container_type = Container;
    using value_compare = Compare;
    using value_type = typename Container::value_type;
    using size_type = typename Container::size_type;
    using reference = typename Container::reference;
    using const_reference = typename Container::const_reference;
    using allocator_type = typename Container::allocator_type;

protected:
    container_type c;
    value_compare comp;

public:
    __GBLIBCPP_CONSTEXPR
    priority_queue(const Compare& comp, const Container& c)
        : c(c), comp(comp)
    {
        std::make_heap(c.begin(), c.end(), comp);
    }

    __GBLIBCPP_CONSTEXPR
    explicit priority_queue(const Compare& comp, Container&& c)
        : c(std::move(c)), comp(comp)
    {
        std::make_heap(c.begin(), c.end(), comp);
    }

    __GBLIBCPP_CONSTEXPR
    priority_queue() : priority_queue(Compare(), Container()) {}

    __GBLIBCPP_CONSTEXPR
    explicit priority_queue(const Compare& comp)
        : priority_queue(comp, Container()) {}

    template <typename InputIter>
    __GBLIBCPP_CONSTEXPR
    priority_queue(InputIter first, InputIter last,
        const Compare& comp = Compare())
        : c(first, last), comp(comp)
    {
        std::make_heap(c.begin(), c.end(), comp);
    }

    template <typename InputIter>
    __GBLIBCPP_CONSTEXPR
    priority_queue(InputIter first, InputIter last,
        const Compare& comp, const Container& c)
        : c(c), comp(comp)
    {
        c.insert(c.end(), first, last);
        std::make_heap(c.begin(), c.end(), comp);
    }

    template <typename InputIter>
    __GBLIBCPP_CONSTEXPR
    priority_queue(InputIter first, InputIter last,
        const Compare& comp, Container&& c)
        : c(std::move(c)), comp(comp)
    {
        c.insert(c.end(), first, last);
        std::make_heap(c.begin(), c.end(), comp);
    }

    __GBLIBCPP_CONSTEXPR
    priority_queue(const priority_queue&) = default;
    __GBLIBCPP_CONSTEXPR
    priority_queue(priority_queue&&) = default;

    __GBLIBCPP_CONSTEXPR
    priority_queue& operator=(const priority_queue&) = default;
    __GBLIBCPP_CONSTEXPR
    priority_queue& operator=(priority_queue&&) = default;

    [[nodiscard]]
    __GBLIBCPP_CONSTEXPR
    bool empty(void) const noexcept { return c.empty(); }
    __GBLIBCPP_CONSTEXPR
    size_type size(void) const noexcept { return c.size(); }
    __GBLIBCPP_CONSTEXPR
    const_reference top(void) const { return c.front(); }

    __GBLIBCPP_CONSTEXPR
    void push(const value_type& val)
    {
        c.push_back(val);
        std::push_heap(c.begin(), c.end(), comp);
    }
    __GBLIBCPP_CONSTEXPR
    void push(value_type&& val)
    {
        c.push_back(std::move(val));
        std::push_heap(c.begin(), c.end(), comp);
    }

    template <typename... Args>
    __GBLIBCPP_CONSTEXPR
    void emplace(Args&&... args)
    {
        c.emplace_back(std::forward<Args>(args)...);
        std::push_heap(c.begin(), c.end(), comp);
    }

    __GBLIBCPP_CONSTEXPR
    void pop(void)
    {
        std::pop_heap(c.begin(), c.end(), comp);
        c.pop_back();
    }

    __GBLIBCPP_CONSTEXPR
    void swap(priority_queue& other) noexcept(
        noexcept(std::swap(c, other.c)) &&
        noexcept(std::swap(comp, other.comp)))
    {
        std::swap(c, other.c);
        std::swap(comp, other.comp);
    }
};

template <typename Compare, typename Container>
priority_queue(Compare, Container)
    -> priority_queue<typename Container::value_type,
        Container, Compare>;

template <typename T, typename Container, typename Compare>
void swap(priority_queue<T, Container, Compare>& lhs,
    priority_queue<T, Container, Compare>& rhs)
    noexcept(noexcept(lhs.swap(rhs)))
{ lhs.swap(rhs); }

} // namespace std

#endif