小菜鸟 的博客

小菜鸟 的博客

配对堆allocator版

posted on 2019-10-14 21:21:29 | under 算法 |
#include<cstdio>
#include<algorithm>
#include<functional>
#include<utility>
#include<memory>

template<typename _Tp,typename _Cmp=std::less<_Tp>,typename _Alloc=std::allocator<_Tp> >
class
pairing_heap:_Cmp
{
    private:
        struct Node;
        Node* _root;
        size_t s;
        Node* merge(Node*,Node*);
        Node* __pop();
        void erase_all_node(Node *ptr);
        typename _Alloc::template rebind<Node>::other __alloc;
    public:
        struct iterator;
        ~pairing_heap();
        iterator push(const _Tp&);
        _Tp top()const;
        iterator pop();
        void join(pairing_heap&);
        bool modify(const iterator&,const _Tp&);
        size_t size();
        bool empty();
};
template<typename _Tp,typename _Cmp,typename _Alloc>
struct
pairing_heap<_Tp,_Cmp,_Alloc>::Node
{
    _Tp value;
    Node *left_node,*child,*sibling;
    Node(const _Tp& val=_Tp()):
        value(val),
        left_node(NULL),
        child(NULL),
        sibling(NULL) {}
};
template<typename _Tp,typename _Cmp,typename _Alloc>
struct
pairing_heap<_Tp,_Cmp,_Alloc>::iterator
{
    private:
        Node* __real_node;
        friend class pairing_heap;
    public:
        _Tp operator*()const {return __real_node->value;}
        operator bool()const {return __real_node!=NULL;}
        bool operator==(const iterator& rhs)const {return __real_node==rhs.__real_node;}
        bool operator!=(const iterator& rhs)const {return __real_node!=rhs.__real_node;}
        iterator(Node* ptr=NULL):__real_node(ptr) {}
        iterator(const iterator& iter):__real_node(iter.__real_node) {}
};
template<typename _Tp,typename _Cmp,typename _Alloc>
pairing_heap<_Tp,_Cmp,_Alloc>::~pairing_heap()
{
    if(_root!=NULL)
    {
        erase_all_node(_root);
    }
}
template<typename _Tp,typename _Cmp,typename _Alloc>
typename
pairing_heap<_Tp,_Cmp,_Alloc>::Node* 
pairing_heap<_Tp,_Cmp,_Alloc>::merge(Node* ptr1,Node* ptr2)
{
    if(ptr1==NULL)return ptr2;
    if(ptr2==NULL)return ptr1;
    if(!_Cmp::operator()(ptr1->value,ptr2->value))std::swap(ptr1,ptr2);
    ptr1->left_node=ptr2;
    ptr1->sibling=ptr2->child;
    if(ptr2->child!=NULL)ptr2->child->left_node=ptr1;
    ptr2->child=ptr1;
    return ptr2;
}
template<typename _Tp,typename _Cmp,typename _Alloc>
typename
pairing_heap<_Tp,_Cmp,_Alloc>::Node*
pairing_heap<_Tp,_Cmp,_Alloc>::__pop()
{
    if(_root==NULL)return NULL;
    Node *son1=_root->child;
    if(son1==NULL)
    {
        return _root=NULL;
    }
    Node *son2=son1->sibling;
    _root->child=son2!=NULL?son2->sibling:NULL;
    son1->left_node=NULL;
    if(son2!=NULL)son2->left_node=NULL;
    return _root=merge(merge(son1,son2),__pop());
}
template<typename _Tp,typename _Cmp,typename _Alloc>
void
pairing_heap<_Tp,_Cmp,_Alloc>::erase_all_node(Node *ptr)
{
    if(ptr->child!=NULL)
    {
        erase_all_node(ptr->child);
    }
    if(ptr->sibling!=NULL)
    {
        erase_all_node(ptr->sibling);
    }
    __alloc.destroy(ptr);
    __alloc.deallocate(ptr,1);
}
template<typename _Tp,typename _Cmp,typename _Alloc>
typename
pairing_heap<_Tp,_Cmp,_Alloc>::iterator
pairing_heap<_Tp,_Cmp,_Alloc>::push(const _Tp& val)
{
    ++s;
    if(_root==NULL)
    {
        _root=__alloc.allocate(1);
        __alloc.construct(_root,val);
        return iterator(_root);
    }
    Node* ptr=__alloc.allocate(1);
    __alloc.construct(ptr,val);
    _root=merge(_root,ptr);
    return iterator(ptr);
}
template<typename _Tp,typename _Cmp,typename _Alloc>
_Tp
pairing_heap<_Tp,_Cmp,_Alloc>::top()const
{
    if(_root==NULL)return _Tp();
    return _root->value;
}
template<typename _Tp,typename _Cmp,typename _Alloc>
typename
pairing_heap<_Tp,_Cmp,_Alloc>::iterator
pairing_heap<_Tp,_Cmp,_Alloc>::pop()
{
    if(_root==NULL)return iterator(NULL);
    --s;
    Node *ptr=_root;
    Node *ret=__pop();
    __alloc.destroy(ptr);
    __alloc.deallocate(ptr,1);
    return iterator(ret);
}
template<typename _Tp,typename _Cmp,typename _Alloc>
void
pairing_heap<_Tp,_Cmp,_Alloc>::join(pairing_heap& heap)
{
    _root=merge(_root,heap._root);
    s+=heap.s;
    heap.s=0;
    heap._root=NULL;
}
template<typename _Tp,typename _Cmp,typename _Alloc>
bool
pairing_heap<_Tp,_Cmp,_Alloc>::modify(const iterator& iter,const _Tp& val)
{
    Node* ptr=iter.__real_node;
    if(iter.__real_node==NULL)return 0;
    if(_Cmp::operator()(val,*iter))
    {
        if(ptr->left_node->child==ptr)
            ptr->left_node->child=ptr->sibling;
        else
            ptr->left_node->sibling=ptr->sibling;
        if(ptr->sibling!=NULL)
            ptr->sibling->left_node=ptr->left_node;
        ptr->left_node=ptr->sibling=NULL;
        Node *changed_node=ptr;
        std::swap(ptr,_root);
        _root=merge(ptr,__pop());
        changed_node->value=val;
        _root=merge(changed_node,_root);
        return 1;
    }
    ptr->value=val;
    if(_root==ptr)
    {
        return 1;
    }
    if(ptr->left_node->child==ptr)
        ptr->left_node->child=ptr->sibling;
    else
        ptr->left_node->sibling=ptr->sibling;
    if(ptr->sibling!=NULL)
        ptr->sibling->left_node=ptr->left_node;
    ptr->left_node=ptr->sibling=NULL;
    _root=merge(_root,ptr);
    return 1;
}
template<typename _Tp,typename _Cmp,typename _Alloc>
size_t
pairing_heap<_Tp,_Cmp,_Alloc>::size()
{
    return s;
}
template<typename _Tp,typename _Cmp,typename _Alloc>
bool
pairing_heap<_Tp,_Cmp,_Alloc>::empty()
{
    return _root==NULL;
}