Heap

/*********************************************************
 *                                                       *
 *                     Template Heap                     *
 *                                                       *
 *     Author - Timur Iskhakov - iskhakovt@gmail.com     *
 *                                                       *
 *********************************************************/



#ifndef _HEAP_
#define _HEAP_

#ifdef __cplusplus

#include <functional>
#include <vector>

#ifndef _ONLY_HEAP_SORT

template < typename Type, class Compare = typename std::less < Type > >
class Heap
{
protected:

    std::vector < Type > List;
    Compare Comp;
    unsigned long minSize;

    static unsigned long const globalMinSize = 0xff;

    typename std::vector < Type >::iterator curr;

    typename std::vector < Type >::iterator begin() const
    {
        return List.begin();
    }

    typename std::vector < Type >::iterator end() const
    {
        return List.end();
    }

    bool compare(Type const &a, Type const &b) const
    {
        return Comp.operator()(a, b);
    }

    void resize(unsigned long const &size)
    {
        List.resize(size);
    }

    typename std::vector < Type >::iterator first_child(typename std::vector < Type >::iterator const &it) const
    {
        if ((it - begin()) * 2 > curr - begin())
        {
            return end();
        }

        return (begin() + (it - begin()) * 2);
    }

    typename std::vector < Type >::iterator parent(typename std::vector < Type >::iterator const &it) const
    {
        return (begin() + (it - begin()) / 2);
    }

    void relax_up(typename std::vector < Type >::iterator it)
    {
        typename std::vector < Type >::iterator par = parent(it);

        while(it != (begin() + 1) && compare(*it, *par))
        {
            std::swap(*it, *par);
            it = par;
            par = parent(it);
        }
    }

    void relax_down(typename std::vector < Type >::iterator it)
    {
        typename std::vector < Type >::iterator first = first_child(it);

        while (first <= curr)
        {
            if (first + 1 <= curr)
            {
                if (compare(*first, *it))
                {
                    if (compare(*(first + 1), *it))
                    {
                        if (compare(*(first + 1), *first))
                        {
                            std::swap(*it, *(first + 1));
                            it = first + 1;
                        }
                        else
                        {
                            std::swap(*it, *first);
                            it = first;
                        }
                    }
                    else
                    {
                        std::swap(*it, *first);
                        it = first;
                    }
                }
                else if (compare(*(first + 1), *it))
                {
                    std::swap(*it, *(first + 1));
                    it = first + 1;
                }
                else
                {
                    return;
                }
            }
            else if (compare(*first, *it))
            {
                std::swap(*it, *first);
                it = first;
            }
            else
            {
                return;
            }

            first = first_child(it);
        }
    }

    static unsigned long getMin(unsigned long const &size)
    {
        return (size < globalMinSize ? globalMinSize : size);
    }

public:

    Heap(unsigned long const &n = 0) : Comp()
    {
        unsigned long maxAmount = 1;
        while (maxAmount <= n)
        {
            maxAmount *= 2;
        }

        resize(maxAmount);
        minSize = Heap::getMin(maxAmount) * 2;

        curr = begin();
    }

    Heap(Heap const &H) : Comp()
    {
        copy(H.begin(), H.end(), begin());
        curr = H.curr - H.begin() + begin();
        minSize = H.minSize();
    }

    template < class Iter >
    Heap(Iter const &Begin, Iter const &End, bool heapified = false) : Comp()
    {
        if (Begin == End)
        {
            resize(0);
            curr = begin();
            return;
        }

        unsigned long maxAmount = 1;
        while (maxAmount <= (End - Begin))
        {
            maxAmount *= 2;
        }

        resize(maxAmount);
        minSize = Heap::getMin(maxAmount) * 2;

        curr = begin();

        if (heapified)
        {
            for (Iter it = Begin; it != End; ++it)
                *(++curr) = *it;
        }
        else
        {
            for (Iter it = Begin; it != End; ++it)
                insert(*it);
        }
    }

    void reserve(unsigned long const &size)
    {
        if (size < end() - begin())
        {
            return;
        }

        unsigned long amount = curr - begin(), maxAmount = 1;
        while (maxAmount <= size)
        {
            maxAmount *= 2;
        }

        resize(maxAmount);
        minSize = Heap::getMin(maxAmount) * 2;
        curr = begin() + amount;
    }

    void insert(Type const &elem)
    {
        if (curr + 1 == end())
        {
            unsigned long amount = curr - begin();
            resize((end() - begin()) * 2);
            curr = begin() + amount;
        }

        *(++curr) = elem;
        relax_up(curr);
    }

    void erase(unsigned long const &n)
    {
        if (n == 1)
        {
            erase_top();
            return;
        }

        if (!n || n > curr - begin())
        {
            throw("Not such element.");
        }

        typename std::vector < Type >::iterator erase = begin() + n;
        std::swap(*erase, *curr--);

        if (compare(*erase, *parent(erase)))
        {
            relax_up(erase);
        }
        else
        {
            relax_down(erase);
        }

        if ((curr - begin()) > minSize && begin() + (end() - begin()) / 2 > curr)
        {
            unsigned long amount = curr - begin();
            resize((end() - begin()) / 2);
            curr = begin() + amount;
        }
    }

    void erase_top()
    {
        if (curr == begin())
        {
            throw("Heap is empty. Nothing to erase.");
        }

        std::swap(*(begin() + 1), *curr--);
        relax_down(begin() + 1);

        if ((curr - begin()) > minSize && begin() + (end() - begin()) / 2 > curr)
        {
            unsigned long amount = curr - begin();
            resize((end() - begin()) / 2);
            curr = begin() + amount;
        }
    }

    void change(unsigned long const &n, Type const &elem)
    {
        typename std::vector < Type >::iterator change = begin() + n;
        *change = elem;

        if (change != begin() + 1 && compare(*change, *parent(change)))
        {
            relax_up(change);
        }
        else
        {
            relax_down(change);
        }
    }

    Type val(unsigned long const &n) const
    {
        if (!n || n > curr - begin())
        {
            throw("Not such element.");
        }

        return *(begin() + n);
    }

    Type top() const
    {
        if (curr == begin())
        {
            throw("Heap is empty. Nothing to return.");
        }

        return *(begin() + 1);
    }

    unsigned long size() const
    {
        return curr - begin();
    }
};

#endif

#ifndef _NO_HEAP_SORT

template < class Iter >
Iter first_child(Iter const &Begin, Iter const &End, Iter const &it)
{
    if ((it - Begin) * 2 >= End - Begin)
    {
        return End;
    }

    return (Begin + (it -Begin) * 2);
}

template < class Iter >
void relax_down(Iter const &Begin, Iter const &End, Iter it)
{
    Iter first = first_child(Begin, End, it);

    while (first < End)
    {
        if (first + 1 < End)
        {
            if (*it < *first)
            {
                if (*it < *(first + 1))
                {
                    if (*(first) < *(first + 1))
                    {
                        std::swap(*it, *(first + 1));
                        it = first + 1;
                    }
                    else
                    {
                        std::swap(*it, *first);
                        it = first;
                    }
                }
                else
                {
                    std::swap(*it, *first);
                    it = first;
                }
            }
            else if (*it < *(first + 1))
            {
                std::swap(*it, *(first + 1));
                it = first + 1;
            }
            else
            {
                return;
            }
        }
        else if (*it < *first)
        {
            std::swap(*it, *first);
            it = first;
        }
        else
        {
            return;
        }

        first = first_child(Begin, End, it);
    }
}

template < class Iter, class Compare >
void relax_down(Iter const &Begin, Iter const &End, Iter it, Compare Comp)
{
    Iter first = first_child(Begin, End, it);

    while (first < End)
    {
        if (first + 1 < End)
        {
            if (Comp(*it, *first))
            {
                if (Comp(*it, *(first + 1)))
                {
                    if (Comp(*first, *(first + 1)))
                    {
                        std::swap(*it, *(first + 1));
                        it = first + 1;
                    }
                    else
                    {
                        std::swap(*it, *first);
                        it = first;
                    }
                }
                else
                {
                    std::swap(*it, *first);
                    it = first;
                }
            }
            else if (Comp(*it, *(first + 1)))
            {
                std::swap(*it, *(first + 1));
                it = first + 1;
            }
            else
            {
                return;
            }
        }
        else if (Comp(*it, *first))
        {
            std::swap(*it, *first);
            it = first;
        }
        else
        {
            return;
        }

        first = first_child(Begin, End, it);
    }
}

template < class Iter >
void heap_sort(Iter const &Begin, Iter const &End)
{
    Iter Last = End - 1;

    for (Iter it = Last; it != Begin; --it)
        relax_down(Begin, End, it);
    relax_down(Begin, End, Begin);

    while (Last != Begin)
    {
        std::swap(*Last, *Begin);
        relax_down(Begin, Last--, Begin);
    }
}

template < class Iter, class Compare >
void heap_sort(Iter const &Begin, Iter const &End, Compare Comp)
{
    Iter Last = End - 1;

    for (Iter it = Last; it != Begin; --it)
        relax_down(Begin, End, it, Comp);
    relax_down(Begin, End, Begin, Comp);

    while (Last != Begin)
    {
        std::swap(*Last, *Begin);
        relax_down(Begin, Last--, Begin, Comp);
    }
}

#endif

#endif
#endif