Aiur/include/Heap.h

Go to the documentation of this file.

#pragma once

#include <vector>
#include <map>
#include <utility>

template <class _Tp,class _Val> 
class Heap
{
private :
        std::vector< std::pair< _Tp, _Val > > data;

        std::map< _Tp, int> mapping;

        bool minHeap;

        int percolate_up(int index);

        int percolate_down(int index);

public :
        Heap(bool isMinHeap = false) : minHeap(isMinHeap) {}
        ~Heap() {}
        void push(std::pair< _Tp, _Val > x);
        void pop();
        const std::pair< _Tp, _Val >& top() const;
        bool set(_Tp& x,_Val& v);
        const _Val& get(_Tp& x) const;

        bool contains(_Tp& x) const;

        bool empty() const;
        int size() const;
        void clear();
        bool erase(_Tp& x);
};

//------------------------------- PERCOLATE UP ---------------------------------
template <class _Tp, class _Val>
int Heap<_Tp,_Val>::percolate_up(int index)
{
        if (index<0 || index>=(int)data.size())
                return -1;
        unsigned int parent=(index-1)/2;
        int m=1;
        if (this->minHeap) m=-1;
        while(index>0 && m*data[parent].second<m*data[index].second)
        {
                std::pair<_Tp,_Val> temp=data[parent];
                data[parent]=data[index];
                data[index]=temp;
                (*mapping.find(data[index].first)).second=index;
                index=parent;
                parent=(index-1)/2;
        }
        (*mapping.find(data[index].first)).second=index;
        return index;
}

//------------------------------ PERCOLATE DOWN --------------------------------
template <class _Tp, class _Val>
int Heap<_Tp,_Val>::percolate_down(int index)
{
        if (index<0 || index>=(int)data.size())
                return -1;
        unsigned int lchild=index*2+1;
        unsigned int rchild=index*2+2;
        unsigned int mchild;
        int m=1;
        if (this->minHeap) m=-1;
        while((data.size()>lchild && m*data[index].second<m*data[lchild].second) ||
                (data.size()>rchild && m*data[index].second<m*data[rchild].second))
        {
                mchild=lchild;
                if (data.size()>rchild && m*data[rchild].second>m*data[lchild].second)
                        mchild=rchild;
                std::pair< _Tp, _Val > temp=data[mchild];
                data[mchild]=data[index];
                data[index]=temp;
                (*mapping.find(data[index].first)).second=index;
                index=mchild;
                lchild=index*2+1;
                rchild=index*2+2;
        }
        (*mapping.find(data[index].first)).second=index;
        return index;
}
//----------------------------------- PUSH -------------------------------------
template <class _Tp, class _Val>
void Heap<_Tp,_Val>::push(std::pair< _Tp, _Val > x)
{
        int index=data.size();
        if (mapping.insert(std::make_pair(x.first,index)).second)
        {
                data.push_back(x);
                percolate_up(index);
        }
}

//----------------------------------- POP --------------------------------------
template <class _Tp, class _Val>
void Heap<_Tp,_Val>::pop()
{
        if (data.empty())
                return;
        mapping.erase(data.front().first);
        data.front()=data.back();
        data.pop_back();
        if (data.empty())
                return;
        std::map<_Tp,int>::iterator iter=mapping.find(data.front().first);
        if (iter!=mapping.end())
        {
                (*iter).second=0;
                percolate_down(0);
        }
}

//----------------------------------- TOP --------------------------------------
template <class _Tp, class _Val>
const std::pair< _Tp, _Val >& Heap<_Tp,_Val>::top() const
{
        return data.front();
}

//---------------------------------- EMPTY -------------------------------------
template <class _Tp, class _Val>
bool Heap<_Tp,_Val>::empty() const
{
        return data.empty();
}

//----------------------------------- SET --------------------------------------
template <class _Tp, class _Val>
bool Heap<_Tp,_Val>::set(_Tp& x,_Val& v)
{
        std::map<_Tp,int>::iterator iter=mapping.find(x);
        if (iter==mapping.end())
        {
                push(std::make_pair(x,v));
                return true;
        }
        int index=(*iter).second;
        data[index].second=v;
        index=percolate_up(index);
        if (index>=0 && index<(int)data.size())
        {
                percolate_down(index);
                return true;
        }
        return false;
}

//----------------------------------- GET --------------------------------------
template <class _Tp, class _Val>
const _Val& Heap<_Tp,_Val>::get(_Tp& x) const
{
        std::map<_Tp,int>::const_iterator iter=mapping.find(x);
        int index=(*iter).second;
        return data[index].second;
}

//--------------------------------- CONTAINS -----------------------------------
template <class _Tp, class _Val>
bool Heap<_Tp,_Val>::contains(_Tp& x) const
{
        std::map<_Tp,int>::const_iterator iter=mapping.find(x);
        return (iter!=mapping.end());
}

//---------------------------------- SIZE --------------------------------------
template <class _Tp, class _Val>
int Heap<_Tp,_Val>::size() const
{
        return data.size();
}

//---------------------------------- CLEAR -------------------------------------
template <class _Tp, class _Val>
void Heap<_Tp,_Val>::clear()
{
        data.clear();
        mapping.clear();
}

//---------------------------------- ERASE -------------------------------------
template <class _Tp, class _Val>
bool Heap<_Tp,_Val>::erase(_Tp& x)
{
        std::map<_Tp,int>::iterator iter=mapping.find(x);
        if (iter==mapping.end())
                return false;
        if (data.size()==1)
                this->clear();
        else
        {
                int index=(*iter).second;
                data[index]=data.back();
                data.pop_back();
                mapping.erase(iter);
                percolate_down(index);
        }
        return true;
}
//------------------------------------------------------------------------------