您是怎么写的??
by runtime_error @ 2019-01-03 11:05:53
```cpp
template<typename T>
class pairing_heap
{
private:
struct Node;
Node* _root;
pairing_heap(Node*);
public:
struct iterator;
pairing_heap():_root(NULL) {}
pairing_heap(const pairing_heap<T>& hp):_root(hp._root) {}
~pairing_heap() {}
iterator insert(const T&);
iterator join(pairing_heap<T>&);
bool modify(const iterator&,const T&);
T top();
void pop();
bool empty();
};
template<typename T>
struct pairing_heap<T>::Node
{
Node* ftr;
Node* son;
Node* prednode;
Node* nextnode;
T val;
Node(T v=T(),Node* f=NULL):val(v),ftr(f),son(NULL),prednode(NULL),nextnode(NULL) {}
};
template<typename T>
struct pairing_heap<T>::iterator
{
private:
Node* _real__node;
public:
T operator*()const{return _real__node->val;}
bool empty(){return _real__node==NULL;}
iterator(pairing_heap hp):_real__node(hp._root) {}
iterator(Node* ptr=NULL):_real__node(ptr) {}
iterator(const pairing_heap<T>::iterator& iter):_real__node(iter._real__node) {}
friend bool pairing_heap<T>::modify(const iterator&,const T&);
};
template<typename T>
pairing_heap<T>::pairing_heap(Node* rt):
_root(rt) {}
template<typename T>
typename
pairing_heap<T>::iterator pairing_heap<T>::insert(const T& v)//插入
{
if(!_root){_root=new Node(v);return iterator(_root);}
pairing_heap<T> temp;
temp.insert(v);
iterator iter(temp);
join(temp);
return iter;
}
template<typename T>
typename
pairing_heap<T>::iterator pairing_heap<T>::join(pairing_heap<T>& hp)//将hp合并至当前堆
{
if(!_root||!hp._root){_root=_root?_root:hp._root;hp._root=NULL;return iterator(_root);}
if(hp._root->val>_root->val)
{
hp._root->ftr=_root;
hp._root->nextnode=_root->son;
if(_root->son)_root->son->prednode=hp._root;
_root->son=hp._root;
hp._root=NULL;
}
else
{
_root->ftr=hp._root;
_root->nextnode=hp._root->son;
if(hp._root->son)hp._root->son->prednode=_root;
hp._root->son=_root;
_root=hp._root;
hp._root=NULL;
}
return iterator(_root);
}
template<typename T>
bool pairing_heap<T>::modify(const iterator& iter,const T& v)//修改iter指向的元素
{
if(v>*iter)return 0;
pairing_heap<T> temp(iter._real__node);
if(iter._real__node->prednode)iter._real__node->prednode->nextnode=iter._real__node->nextnode;
if(iter._real__node->nextnode)iter._real__node->nextnode->prednode=iter._real__node->prednode;
join(temp);
}
template<typename T>
T pairing_heap<T>::top()
{
return _root->val;
}
template<typename T>
void pairing_heap<T>::pop()
{
if(!_root)return;
if(!_root->son){delete _root;_root=NULL;return;}
queue<pairing_heap> q;
for(Node* i=_root->son;i;i=i->nextnode)
{
q.push(pairing_heap(i));
}
while(q.size()>1)
{
pairing_heap<T> a(q.front());
q.pop();
pairing_heap<T> b(q.front());
q.pop();
a.join(b);
q.push(a);
}
*this=q.front();
q.pop();
}
template<typename T>
bool pairing_heap<T>::empty()
{
return _root?0:1;
}
```
@[runtime_error](/space/show?uid=92605) 码风不好,大佬不要喷我QAQ
by 小菜鸟 @ 2019-01-03 11:16:53
里面用的queue也是我手打的
by 小菜鸟 @ 2019-01-03 11:17:24
~~配对堆的正确使用方法:~~
```
#include <ext/pb_ds/priority_queue.hpp>
using namespace __gnu_pbds;
__gnu_pbds::priority_queue< int, greater<int>,
__gnu_pbds::pairing_heap_tag > pq;
```
by Prurite @ 2019-01-03 11:23:38
@[小菜鸟](/space/show?uid=60489) 您用的是java吧,c++ 蒟蒻表示看不懂(orz
by runtime_error @ 2019-01-03 11:23:40
@[runtime_error](/space/show?uid=92605) orz我才是c++蒟蒻啊
by 小菜鸟 @ 2019-01-03 11:25:49
@[星烁晶熠辉](/space/show?uid=54160) 大佬不要吓唬不看平板电视的蒟蒻QAQ
by 小菜鸟 @ 2019-01-03 11:26:34
@[runtime_error](/space/show?uid=92605) ~~您如果连面向对象和模板都不了解的话,您学的怕不是C with STL~~
by Prurite @ 2019-01-03 11:27:26
@[星烁晶熠辉](/space/show?uid=54160) 对啊,蒟蒻还没学那些,现在还停留在竞赛(orz
by runtime_error @ 2019-01-03 11:31:45
@[runtime_error](/space/show?uid=92605) Orz我不会告诉您~~我是挂在pj初赛的蒟蒻~~
by 小菜鸟 @ 2019-01-03 11:34:47