由于博主很弱，只会打板子，请见谅

配对堆

一种极其好写又极其快速的堆

先看复杂度

空间复杂度：\Theta(n)
时间复杂度：
插入：\Theta(1)
合并：\Theta(1)
查询最值：\Theta(1)
删除元素：O(log\,n)(均摊)
修改元素：下界\Omega(log\,log\,n)，上界O(2^{2\sqrt{log\,log\,n}})(均摊)?反正就是O(玄学)

在进操作之前，先看看配对堆的结构

强行模仿STL源码码风警告

不熟练的面向对象及封装警告

配对堆是一种堆有序多叉树。根据要完成的操作，可以给出对该类的定义

template<typename _Tp,typename _Cmp=std::less<_Tp> >
class pairing_heap:private _Cmp
{
    typedef _Tp value_type;
    typedef _Cmp compare;
    private:
        struct Node;//单个元素结点
        Node* _root;//根指针
        size_t s;//记录堆的大小
        Node* merge(Node*,Node*);//合并两个堆的内部实现
        Node* __pop();//删除函数的内部实现
    public:
        struct iterator;//迭代器
        iterator push(const _Tp&);//在堆中压入新元素
        _Tp top()const;//取堆顶
        iterator pop();//删除堆顶元素
        void join(pairing_heap&);//合并两个堆
        bool modify(const iterator&,const _Tp&);//将某位置的值修改
        size_t size();//不做解释
        bool empty();
};

对每个结点，需维护其父亲及所有的儿子。为了方便在修改元素时将结点分离出来，这里采用双向链表来维护其儿子。具体地讲，父亲的child指针指向第一个儿子，同时每个结点又带有指向右兄弟的指针域。每个结点还有一个“左结点”：对于有左兄弟的结点即为左兄弟，否则为父结点。这种存储方法被称为“左儿子右兄弟”（似乎广义表就是这么存的？）。
来看看图
这是原来的堆

这是堆的实际存储方式

还是很好理解的QWQ

结点的结构体

template<typename _Tp,typename _Cmp>
struct
pairing_heap<_Tp,_Cmp>::Node
{
    _Tp value;
    Node *left_node,*child,*sibling;
    //left_node即“左结点”，child指向最左侧的儿子，sibling指向右兄弟
    Node(const _Tp& val=_Tp()):
        value(val),
        left_node(NULL),
        child(NULL),
        sibling(NULL) {}
};

为了修改权值，再写出指向元素的迭代器

template<typename _Tp,typename _Cmp>
struct
pairing_heap<_Tp,_Cmp>::iterator
{
    private:
        Node* __real_node;
        friend class pairing_heap;
    public:
        _Tp operator*()const {return __real_node->value;}
        bool operator==(void* ptr){return __real_node==ptr;}
        bool operator!=(void* ptr){return __real_node!=ptr;}
        iterator(Node* ptr=NULL):__real_node(ptr) {}
        iterator(const iterator& iter):__real_node(iter.__real_node) {}
};

前置结构知识完

下面进操作

内部函数

1.合并两个配对堆

很简单，直接比较两个根的大小，把大根接到小根的儿子表里就好辣！
-->合并后

为什么不先讲插入？因为插入就是把只有一个元素的堆合并进去。。。

template<typename _Tp,typename _Cmp>
typename
pairing_heap<_Tp,_Cmp>::Node* 
pairing_heap<_Tp,_Cmp>::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);
    //以上和左偏树很像~
    ptr2->left_node=ptr1;//直接把ptr2插入到ptr1儿子链表的左侧
    ptr2->sibling=ptr1->child;
    if(ptr1->child!=NULL)ptr1->child->left_node=ptr2;
    ptr1->child=ptr2;
    return ptr1;
}

显然，比较是O(1)的，链表插入也是O(1)的，因此整个合并操作也是O(1)的。
更简单的计算：你看我根本没用循环和递归对不对？

2.删除堆顶元素

一种显而易见的方法：直接暴力合并所有子树，单次复杂度O(儿子个数)，最高O(n)。
然而这样真的好吗？
用这种方法删除，最坏状况下新堆的根结点的儿子数仍是O(n)！而这将导致后续删除操作的复杂度大大提高，显然与开始说均摊复杂度O(logn)不符。
那么如何优化呢？
下面是配对堆的灵魂所在，也是其名字的来源。
将儿子两两合并至原先数目的一半，再重复这个过程直至只剩1个堆，即为删除堆顶后的新堆。
复杂度最高O(\frac{n}{2}+\frac{n}{4}+\frac{n}{8}+···)=O(n)
似乎没有变快？
但是新堆根结点的儿子个数少了！！！
来这么考虑：
假设共n棵需合并的子树
从n=1开始

什么也不用做，新根的儿子数O(0)手动滑稽

n=2

儿子数为1

n=4

儿子数为2

n=8

儿子数为3
发现了什么？
用这种方法，一次删除后儿子数变成了O(logn)!
正是因为要一对一对地合并，这个骨骼清奇的数据结构才被冠以“配对堆”的诨号。这种合并方式使得在一次删除之后，再次删除时不可能出现最坏情况。因此在多次删除时，就算最开始为最坏情况，后续操作的平均复杂度也会逐渐稳定在O(logn)左右。
（注：这种理解只适用于队列的log_2 n趟合并，递归只合并了两趟，以略多的子树个数来换取单次合并的较小常数）
这里给出两种合并的方式，递归式合并和队列式合并
不开O2时队列版慢得飞起，开了略快于递归版

//递归版
template<typename _Tp,typename _Cmp>
typename
pairing_heap<_Tp,_Cmp>::Node*
pairing_heap<_Tp,_Cmp>::__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
pairing_heap<_Tp,_Cmp>::Node*
pairing_heap<_Tp,_Cmp>::__pop()
{
    if(_root==NULL)return NULL;
    Node *son1=_root->child,*son2;
    if(son1==NULL)
    {
        return _root=NULL;
    }
    std::queue<Node*> que;
    for(Node* ptr=son1;ptr!=NULL;ptr=ptr->sibling)que.push(ptr);
    while(que.size()>1)
    {
        son1=que.front();
        que.pop();
        son2=que.front();
        que.pop();
        son1->left_node=son1->sibling=NULL;
        son2->left_node=son2->sibling=NULL;
        que.push(merge(son1,son2));
        //每次取队首两子树合并
        //然后再进入队列
    }
    delete _root;
    if(que.empty())return _root=NULL;
    return _root=que.front();
}

外部接口

1.插入

不必赘述。。。

template<typename _Tp,typename _Cmp>
typename
pairing_heap<_Tp,_Cmp>::iterator
pairing_heap<_Tp,_Cmp>::push(const _Tp& val)
{
    ++s;//维护一下size
    if(_root==NULL)
    {
        _root=new Node(val);
        return iterator(_root);
    }
    Node* ptr=new Node(val);
    _root=merge(_root,ptr);
    return iterator(ptr);
}

2.删除堆顶元素

//把新的根包装成迭代器返回出来
template<typename _Tp,typename _Cmp>
typename
pairing_heap<_Tp,_Cmp>::iterator
pairing_heap<_Tp,_Cmp>::pop()
{
    if(_root==NULL)return iterator(NULL);
    --s;
    Node *ptr=_root;
    Node *ret=__pop();
    delete ptr;//__pop并没有释放空间，这里释放一下
    return iterator(ret);
}

3.查询堆顶元素

由于每个配对堆都是堆有序的，因此直接返回根值就行了。
复杂度显然也是O(1)，注意判断空堆的情况

template<typename _Tp,typename _Cmp>
_Tp
pairing_heap<_Tp,_Cmp>::top()const
{
    if(_root==NULL)return _Tp();//如果堆为空，返回零
    return _root->value;
}

4.合并两个堆

只是调用内部函数，没什么好说的

//把一个堆中所有元素加入另一个堆中
template<typename _Tp,typename _Cmp>
void
pairing_heap<_Tp,_Cmp>::join(pairing_heap& heap)
{
    _root=merge(_root,heap._root);
    s+=heap.s;//注意清空另一个堆
    heap.s=0;
    heap._root=NULL;
}

5.【神级操作】修改元素值

思路相当好理解，把以该结点为根的子树从树里拆出来，修改值（确切地说，小根堆为减小值，大根堆为增大值）以后再合并回去即可。代码细节要注意一下，各种兄弟指针啥的记得归零QAQ

template<typename _Tp,typename _Cmp>
bool
pairing_heap<_Tp,_Cmp>::modify(const iterator& iter,const _Tp& val)
{
    if(iter.__real_node==NULL||_Cmp::operator()(val,*iter))return 0;//不能修改的情况判一下
    Node* ptr=iter.__real_node;
    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;
}

6.两个附加接口

就是STL里最常用的，很简单的辣！

template<typename _Tp,typename _Cmp>
size_t
pairing_heap<_Tp,_Cmp>::size()
{
    return s;
}
template<typename _Tp,typename _Cmp>
bool
pairing_heap<_Tp,_Cmp>::empty()
{
    return _root==NULL;
}

最后，如何使用这个板子？
最前面：

#include<algorithm>
#include<functional>

在需要的地方写上以下内容

pairing_heap<数据类型,比较算子> 堆名;

其中比较算子用less为大根堆，用greater为小根堆（直接沿用STL的习惯） 其他用法和STL、pb_ds里面的priority_queue相同。
完结撒花！ヾ(◍°∇°◍)ﾉﾞ

后记： 博主在学配对堆的前一天刚学了左偏树。本来以为已经是最好用的可并堆了，却在题解中偶然看到了配对堆，瞬间被它易懂的思想、简短的代码貌似被封装过也不短了和优异的时间复杂度震撼了，因此进行了学习。这里挂出所有我参考过的博文
博文1（似乎并不是OIer）
博文2（似乎是奆佬）
博文3（似乎还是奆佬）

复杂度参考了维基百科 中文站有时进不去，点这个

（还是进不去？你需要一架梯子。）

2019.2.20 upd

由于先前博主贴的为早期制杖代码，今天将代码完全重写并放上，实测与pb_ds库中优先队列功能无差异~用来写Dijkstra、代替大部分左偏树还是很好的ヾ(●´∀｀●)
另外再附一些可以套这个板子的题目
P3371
P4779
P1552
P3378

2019.2.26 upd

对于modify函数，可以用奇怪的方法在小根堆中增大键值。代码如下

template<typename _Tp,typename _Cmp>
bool
pairing_heap<_Tp,_Cmp>::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;
        changed_node->child=NULL;
        _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;
}

2019.10.15 upd

将空间分配重写成了分配器的方式，可以支持与STL相同的分配方式QwQ

具体代码详见这篇（后续代码改动都在这里）

2019.10.18 upd

重写了析构函数以避免内存泄漏