小菜鸟 的博客

小菜鸟 的博客

配对堆学习笔记&&模板

posted on 2019-02-20 22:21:09 | under 算法 |

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

配对堆

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

先看复杂度

空间复杂度:$\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

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