二项堆(Binominal Heap)

可合并堆简介

有时候我们面临着合并两个堆的需求，举个栗子：
某市有俩医院，分别用一个优先级队列记录病人就医顺序，但是突然一家医院设施全部瘫痪所以病人需要迁移到另一所医院就医，那么该怎样将这个两个优先级队列合并成一个新的优先级队列呢？
另外有些图算法也依赖优先级队列的合并。

两个最大堆怎么合并？

假设我们原先用普通的二叉堆来实现优先级队列，那么并没有比较好的合并二者的方法，只有简单的merge两个数列然后重新调用buildHeap函数,这个时间复杂度为O(n)。看起来并不算太差，但我们希望更好。
我们定义可支持高效合并的堆为可合并堆（meldable heap），显然普通的二叉堆并不是可合并堆，因为其合并复杂度有点高。我们怎样构造一种可合并堆呢？

The Intuition

合并堆的过程和数值加法有神似

二进制加法

二进制加法复杂度为O(max{log(a),log(b)}),如果我们能类比二进制加法来定制一个堆，那么合并复杂度就是log(n)级别的！

类比

我们将堆表示为多个个数为2的自然数幂的“packet”
[图片上传失败...(image-824d30-1515069102116)]

类比堆
那么将堆合并就可以看做每个对应位的“packet”结合、进位
类比

packet

为了支持可合并堆，我们对packet有以下要求：
1.包含元素的个数必须为2的自然数幂
2.要能以O(1)的时间复杂度高度合并两个相同大小的packet
3.要能以O(1)的时间找到每个packet的最值
4.能高效拆分成含有1，1，2，4，...，2^(n-1)个元素的子 packet（删除元素要用！）

k阶二项树

对于上述要求的 packet 我们使用 k 阶二项树来实现。一个k阶二项树递归定义如下：
儿子们有且只含有一个k-1阶二项树、k-2阶二项树、... 、1阶二项树、0阶二项树的树称为k阶二项树。其中0阶二项树表示只含有一个根节点的树。
我们定义二项树（packet）所应该含有的属性如下：

//packet 大小
size_t size=0;
//根元素，同时表示该packet最小值
T key;
//用list表示的儿子元素指针
list<shared_ptr<packet<T>>>son;
//该二项树所挂靠的树
shared_ptr<packet<T>> parent;

对于上述 packet 要求：

1.数学归纳法易证一个k阶二项树含有 2^k 个节点。
2.合并两个相同大小的 packet：
只需要根据堆的类型将其中一个二项树“挂到”另一个二项树下面称为第一个子节点即可，以最小堆为例:

mergepacket

friend shared_ptr<packet<T>> meldTwoPackets
(shared_ptr<packet<T>> p1,shared_ptr<packet<T>> p2){
    //处理其中一个为空的特殊情形
    if(p1->size==0){
        return p2;
    }
    if(p2->size==0){
        return p1;
    }
    //将key较大者挂靠在较小的二项树下
    if(p1->key<p2->key){
        p2->parent=p1;
        p1->son.push_front(p2);
        p1->size*=2;
        return p1;
    }else{
        p1->parent=p2;
        p2->son.push_front(p1);
        p2->size*=2;
        return p2;
    }
}

3.显然根节点即为最值，将其取出即可，耗时O(1)。

T top(){
    return key;
}

4.显然把根节点删除后天然形成 n 个子树，耗时O(1)。

删除根节点后剩余节点

堆序二项树（heap-ordered binominal tree）

满足最大（小）堆性质的二项树称为堆序二项树。即：
一个最大堆序二项树满足所有的父节点都不小于其子节点。
一个最小堆序二项树满足所有的父节点都不大于其子节点。

二项堆(Binominal Heap)

由一组堆序二项树按照 size 大小单调排列的、并且每种 size 的二项树至多只有一个，构成的数据结构称为二项堆(Binominal Heap)。其属性用一个vector在相应位置存储各个二项树即可。

vector<shared_ptr<packet<T>>> binominalTrees;

合并——meldWith()

这个是二项堆的核心方法，几乎所有的其它操作都依赖这个方法来实现。其操作过程和链表实现二进制加法很类似，具体讲解详见代码

void meldWith(shared_ptr<binominalHeap<T>> another){
   size_t i;
   //表示“进位”
   shared_ptr<packet<T>> bonus=make_shared<packet<T>>();
   size_t i_position_size=1;
   //结果的“位数”肯定不小于加数的“位数”，所以融合前先补位
   if(another->getBinominalTress().size()>this->binominalTrees.size()){
       for(size_t extra=0;extra<another->getBinominalTress().size()-this->binominalTrees.size();extra++){
           this->binominalTrees.push_back(make_shared<packet<T>>());
       }
   }
   //逐“位”融合
   for(i=0;i<another->getBinominalTress().size();i++){
       //先不考虑“进位”进行融合
       shared_ptr<packet<T>> tmp=meldTwoPackets(this->binominalTrees[i],another->getBinominalTress()[i]);
       //case1：融合后size为0
       //此时本位的二项树肯定就是进位的二项树，而进位二项树变为空树。
       if(tmp->size==0){
           this->binominalTrees[i]=bonus;
           bonus=make_shared<packet<T>>();
       }
       //case2：融合后size和本位size一样大
       //此时情况较复杂，需要继续和进位二项树融合看结果
       else if(tmp->size==i_position_size){
           tmp=meldTwoPackets(tmp,bonus);
           //case2.1：完整融合二项树和本位size一样大
           //那么本位的二项树就是完整融合二项树，进位空树
           if(tmp->size==i_position_size){
               this->binominalTrees[i]=tmp;
               bonus=make_shared<packet<T>>();
           }
           //case2.2：完整融合二项树是本位size两倍大
           //那么进位的二项树就是完整融合二项树，本位空树
           else{
               this->binominalTrees[i]=make_shared<packet<T>>();
               bonus=tmp;
           }
       }
       //case3：融合后size为本位对应size的两倍大，表示进位
       //此时进位为部分融合树，本位的二项树肯定就是进位的二项树
       else{
           this->binominalTrees[i]=bonus;
           bonus=tmp;
       }
       i_position_size<<=1;
   }
   //还没完，如果仍有进位二项树则继续处理。
   if(bonus->size>0){
       //此时只有两部分融合：进位二项树和原二项树
       for(size_t j=i;j<this->binominalTrees.size();j++){
            shared_ptr<packet<T>> tmp=meldTwoPackets(this->binominalTrees[j],bonus);
            //case1:如果此时融合size和本位size一样大，说明没有“进位”
            //本位二项树即为融合树，进位为空树，并且所有融合过程就此结束
            if(tmp->size==i_position_size){
                this->binominalTrees[j]=tmp;
                bonus=make_shared<packet<T>>();
                break;
            }
            //case2:如果此时融合size是本位size两倍大，则“进位”
            //本位二项树为空树，进位为融合树，继续融合。
            else{
                this->binominalTrees[j]=make_shared<packet<T>>();
                bonus=tmp;
            }
            i_position_size<<=1;
       }
       //一种特殊情况，若遇到最高位进位，则push_back(bonus)
       //例如：二进制1111+1会发生这种情况。
       if(bonus->size>0){
           this->binominalTrees.push_back(bonus);
       }
   }
}

添加新元素——push()

可以看做原有二项堆和一个只有单个元素的二项堆的合并，时间复杂度O(log(n))

二叉堆 push

void push(const T& x){
    //只有一个元素的二项树
    auto one=make_shared<binominalHeap<T>>(x);
    this->meldWith(one);
}

查找最小元素——top()

遍历所有子二项树，查找最小值，耗时O(1)*O(log(n))=O(log(n))

//只有size>0的二项树key才真正有意义
T top(){
    auto iter=binominalTrees.cbegin();
    while((*iter)->size==0){
        iter++;
    }
    T result= (*iter)->top();
    for(;iter!=binominalTrees.cend();iter++){
        if((*iter)->size>0){
            if((*iter)->top()<result){
                result=(*iter)->top();
            }
        }
    }
    return result;
}

删除最小元素——pop()

含有最小元素的那个packet去掉一个元素后就不满足大小为2的自然数幂了额。不过一个有趣的事实是：
$$2^{n-1=\sum_{i=0}}{n-1}2^i$$
所以我们可以将删掉元素的那个 packet 拆分为 n 个子 packet 构成的二项堆（这就是为什么要求 packet 支持高效拆分的理由），然后进行两个堆的合并即可。其时间复杂度为O(1+log(n))=)(log(n))。

void pop(){
    //定位要删除的元素下标
    auto iter=binominalTrees.cbegin();
    while((*iter)->size==0){
        iter++;
    }
    T result= (*iter)->top();
    size_t min_position=iter-binominalTrees.cbegin();
    for(;iter!=binominalTrees.cend();iter++){
        if((*iter)->size>0){
            if((*iter)->top()<result){
                result=(*iter)->top();
                min_position=iter-binominalTrees.cbegin();
            }
        }
    }
    //删除根，并由子二项树链表构成新二项堆，融合即可
    auto remain=binominalTrees[min_position]->son;
    if(remain.size()>0){
        remain.reverse();
        binominalHeap<T> another;
        for(auto iter=remain.begin();iter!=remain.end();iter++){
            (*iter)->parent=nullptr;
            another.binominalTrees.push_back(*iter);
        }
        binominalTrees[min_position]=make_shared<packet<T>>();
        meldWith(another);
    }
}

完整序列操作演示

一段完整的二项树添加元素、合并、删除元素过程如下所示：

完整序列操作

摊还分析

1.若只push元素，那么平均复杂度为O(1)，这说明从0构建一个有n个元素二项堆时间复杂度为O(n)，而从0逐项构建二叉堆时间复杂度为O(nlog(n))!
2.当有删除操作时，摊还分析复杂度并不成立。因为处于边界情形时交替进行插入、删除操作会持续导致O(log(n))的操作，进行k次则整体复杂度恶化为O(klog(n))

瘫痪分析失效

总结与展望

本文主要介绍了一种可合并堆——二项堆。首先将其和二进制加法进行了类比，然后引出其基本实现元素——二项树，并利用二项树构成二项堆。然后本文大致介绍了其代码实现，同时指出了其在面临边界特殊情形时操作时间复杂度变差的理由。
为了规避这一风险，我们后面将介绍 lazy 二项堆。
同时二项堆仍没有解决decrease key难题，后面将介绍斐波那契堆。
如果觉得这种可合并堆实现比较复杂，那么后面介绍的左倾堆实现起来就很简单啦。

Acknowledgement

本文大部分动图都来自Keith Schwarz@Stanford，向其表示感谢！