配对堆allocator版
小菜鸟
2019-10-14 21:21:29
```cpp
#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;
}
```