配对堆学习笔记&&模板

**由于博主很弱，只会打板子，请见谅** # 配对堆 # 一种极其好写又极其快速的堆 先看复杂度 空间复杂度：$\Theta(n)$ 时间复杂度： 插入：$\Theta(1)$ 合并：$\Theta(1)$ 查询最值：$\Theta(1)$ 删除元素：$O(log\,n)$(均摊) 修改元素：下界$\Omega(log\,log\,n)$，上界$O(2^{2\sqrt{log\,log\,n}})$(均摊)?~~反正就是~~$O($~~玄学~~$)$ 在进操作之前，先看看配对堆的结构 ~~强行模仿STL源码码风警告~~ ~~不熟练的面向对象及封装警告~~ 配对堆是一种堆有序**多叉树**。根据要完成的操作，可以给出对该类的定义 ```cpp 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 结点的结构体 ```cpp 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) {} }; ``` 为了修改权值，再写出指向元素的迭代器 ```cpp 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.合并两个配对堆 ## 很简单，直接比较两个根的大小，把大根接到小根的儿子表里就好辣！  -->合并后  为什么不先讲插入？因为插入就是把只有一个元素的堆合并进去。。。 ```cpp 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时队列版慢得飞起，开了略快于递归版 ```cpp //递归版 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()); //依次找出最左侧的两个儿子进行合并 } ``` ```cpp //队列版 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.插入 ## 不必赘述。。。 ```cpp 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.删除堆顶元素 ## ```cpp //把新的根包装成迭代器返回出来 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)$，注意判断空堆的情况 ```cpp template<typename _Tp,typename _Cmp> _Tp pairing_heap<_Tp,_Cmp>::top()const { if(_root==NULL)return _Tp();//如果堆为空，返回零 return _root->value; } ``` ## 4.合并两个堆 ## 只是调用内部函数，没什么好说的 ```cpp //把一个堆中所有元素加入另一个堆中 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 ```cpp 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里最常用的，很简单的辣！ ```cpp 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; } ``` 最后，如何使用这个板子？ 最前面： ```cpp #include<algorithm> #include<functional> ``` 在需要的地方写上以下内容 ```cpp pairing_heap<数据类型,比较算子> 堆名; ``` 其中比较算子用less为大根堆，用greater为小根堆（直接沿用STL的习惯） 其他用法和STL、pb_ds里面的priority_queue相同。 完结撒花！ヾ(◍°∇°◍)ﾉﾞ --- 后记： 博主在学配对堆的前一天刚学了左偏树。本来以为已经是最好用的可并堆了，却在题解中偶然看到了配对堆，瞬间被它易懂的思想、简短的代码~~貌似被封装过也不短了~~和优异的时间复杂度震撼了，因此进行了学习。这里挂出所有我参考过的博文 [博文1（似乎并不是OIer）](https://blog.csdn.net/ljsspace/article/details/6751900) [博文2（似乎是奆佬）](https://blog.csdn.net/PhilipsWeng/article/details/48087865) [博文3（似乎还是奆佬）](https://blog.csdn.net/HelloHitler/article/details/81304449) 复杂度参考了[维基百科](https://zh.wikipedia.org/wiki/配对堆) 中文站有时进不去，点[这个](https://en.wikipedia.org/wiki/pairing_heap) （还是进不去？你需要一架梯子。） --- ## 2019.2.20 upd 由于先前博主贴的为早期制杖代码，今天将代码完全重写并放上，实测与pb_ds库中优先队列功能无差异~用来写Dijkstra、代替大部分左偏树还是很好的ヾ(●´∀｀●) 另外再附一些可以套这个板子的题目 [P3371](https://www.luogu.org/problemnew/show/P3371) [P4779](https://www.luogu.org/problemnew/show/P4779) [P1552](https://www.luogu.org/problemnew/show/P1552) [P3378](https://www.luogu.org/problemnew/show/P3378) --- ## 2019.2.26 upd 对于$modify$函数，可以用奇怪的方法在小根堆中增大键值。代码如下 ```cpp 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 具体代码详见[这篇](https://www.luogu.org/blog/surf/pairing-heap-allocator)（后续代码改动都在这里） --- ## 2019.10.18 upd 重写了析构函数以避免内存泄漏