可合并堆簡介
有時候我們面臨著合并兩個堆的需求猖败，舉個栗子：
某市有倆醫(yī)院哈扮，分別用一個優(yōu)先級隊列記錄病人就醫(yī)順序捆探，但是突然一家醫(yī)院設(shè)施全部癱瘓所以病人需要遷移到另一所醫(yī)院就醫(yī)守伸，那么該怎樣將這個兩個優(yōu)先級隊列合并成一個新的優(yōu)先級隊列呢？
另外有些圖算法也依賴優(yōu)先級隊列的合并辕漂。
假設(shè)我們原先用普通的二叉堆來實現(xiàn)優(yōu)先級隊列，那么并沒有比較好的合并二者的方法钉嘹，只有簡單的merge兩個數(shù)列然后重新調(diào)用buildHeap函數(shù),這個時間復(fù)雜度為O(n)鸯乃。看起來并不算太差跋涣，但我們希望更好缨睡。
我們定義可支持高效合并的堆為可合并堆（meldable heap），顯然普通的二叉堆并不是可合并堆陈辱，因為其合并復(fù)雜度有點高奖年。我們怎樣構(gòu)造一種可合并堆呢？
The Intuition
合并堆的過程和數(shù)值加法有神似
二進制加法復(fù)雜度為O(max{log(a),log(b)}),如果我們能類比二進制加法來定制一個堆沛贪，那么合并復(fù)雜度就是log(n)級別的陋守！
類比
我們將堆表示為多個個數(shù)為2的自然數(shù)冪的“packet”
[圖片上傳失敗...(image-824d30-1515069102116)]
那么將堆合并就可以看做每個對應(yīng)位的“packet”結(jié)合、進位
packet
為了支持可合并堆利赋，我們對packet有以下要求：
1.包含元素的個數(shù)必須為2的自然數(shù)冪
2.要能以O(shè)(1)的時間復(fù)雜度高度合并兩個相同大小的packet
3.要能以O(shè)(1)的時間找到每個packet的最值
4.能高效拆分成含有1水评，1，2隐砸，4，...蝙眶，2^(n-1)個元素的子 packet（刪除元素要用＜鞠！）
k階二項樹
對于上述要求的 packet 我們使用 k 階二項樹來實現(xiàn)褪那。一個k階二項樹遞歸定義如下：
兒子們有且只含有一個k-1階二項樹、k-2階二項樹式塌、... 博敬、1階二項樹、0階二項樹的樹稱為k階二項樹峰尝。其中0階二項樹表示只含有一個根節(jié)點的樹偏窝。
我們定義二項樹（packet）所應(yīng)該含有的屬性如下：
//packet 大小
size_t size=0;
//根元素，同時表示該packet最小值
T key;
//用list表示的兒子元素指針
list<shared_ptr<packet<T>>>son;
//該二項樹所掛靠的樹
shared_ptr<packet<T>> parent;
對于上述 packet 要求：
1.數(shù)學(xué)歸納法易證一個k階二項樹含有 2^k 個節(jié)點武学。
2.合并兩個相同大小的 packet：
只需要根據(jù)堆的類型將其中一個二項樹“掛到”另一個二項樹下面稱為第一個子節(jié)點即可祭往，以最小堆為例:
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.顯然根節(jié)點即為最值，將其取出即可火窒，耗時O(1)硼补。
T top(){
return key;
}
4.顯然把根節(jié)點刪除后天然形成 n 個子樹，耗時O(1)熏矿。
堆序二項樹（heap-ordered binominal tree）
滿足最大（幸押А）堆性質(zhì)的二項樹稱為堆序二項樹。即：
一個最大堆序二項樹滿足所有的父節(jié)點都不小于其子節(jié)點票编。
一個最小堆序二項樹滿足所有的父節(jié)點都不大于其子節(jié)點褪储。
二項堆(Binominal Heap)
由一組堆序二項樹按照 size 大小單調(diào)排列的、并且每種 size 的二項樹至多只有一個慧域，構(gòu)成的數(shù)據(jù)結(jié)構(gòu)稱為二項堆(Binominal Heap)鲤竹。其屬性用一個vector在相應(yīng)位置存儲各個二項樹即可。
vector<shared_ptr<packet<T>>> binominalTrees;
合并——meldWith()
這個是二項堆的核心方法吊趾，幾乎所有的其它操作都依賴這個方法來實現(xiàn)宛裕。其操作過程和鏈表實現(xiàn)二進制加法很類似，具體講解詳見代碼
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;
//結(jié)果的“位數(shù)”肯定不小于加數(shù)的“位數(shù)”论泛，所以融合前先補位
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
//此時本位的二項樹肯定就是進位的二項樹揩尸，而進位二項樹變?yōu)榭諛洹? if(tmp->size==0){
this->binominalTrees[i]=bonus;
bonus=make_shared<packet<T>>();
}
//case2：融合后size和本位size一樣大
//此時情況較復(fù)雜，需要繼續(xù)和進位二項樹融合看結(jié)果
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為本位對應(yīng)size的兩倍大，表示進位
//此時進位為部分融合樹坟瓢，本位的二項樹肯定就是進位的二項樹
else{
this->binominalTrees[i]=bonus;
bonus=tmp;
}
i_position_size<<=1;
}
//還沒完勇边，如果仍有進位二項樹則繼續(xù)處理。
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一樣大折联，說明沒有“進位”
//本位二項樹即為融合樹粒褒，進位為空樹，并且所有融合過程就此結(jié)束
if(tmp->size==i_position_size){
this->binominalTrees[j]=tmp;
bonus=make_shared<packet<T>>();
break;
}
//case2:如果此時融合size是本位size兩倍大诚镰，則“進位”
//本位二項樹為空樹奕坟，進位為融合樹祥款，繼續(xù)融合。
else{
this->binominalTrees[j]=make_shared<packet<T>>();
bonus=tmp;
}
i_position_size<<=1;
}
//一種特殊情況月杉，若遇到最高位進位刃跛，則push_back(bonus)
//例如：二進制1111+1會發(fā)生這種情況。
if(bonus->size>0){
this->binominalTrees.push_back(bonus);
}
}
}
添加新元素——push()
可以看做原有二項堆和一個只有單個元素的二項堆的合并苛萎，時間復(fù)雜度O(log(n))
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的自然數(shù)冪了額腌歉。不過一個有趣的事實是：
$$2n-1=\sum_{i=0}{n-1}2^i$$
所以我們可以將刪掉元素的那個 packet 拆分為 n 個子 packet 構(gòu)成的二項堆（這就是為什么要求 packet 支持高效拆分的理由）蛙酪，然后進行兩個堆的合并即可。其時間復(fù)雜度為O(1+log(n))=)(log(n))究履。
void pop(){
//定位要刪除的元素下標(biāo)
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();
}
}
}
//刪除根滤否，并由子二項樹鏈表構(gòu)成新二項堆，融合即可
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元素，那么平均復(fù)雜度為O(1)泥彤，這說明從0構(gòu)建一個有n個元素二項堆時間復(fù)雜度為O(n)欲芹，而從0逐項構(gòu)建二叉堆時間復(fù)雜度為O(nlog(n))!
2.當(dāng)有刪除操作時，攤還分析復(fù)雜度并不成立吟吝。因為處于邊界情形時交替進行插入菱父、刪除操作會持續(xù)導(dǎo)致O(log(n))的操作，進行k次則整體復(fù)雜度惡化為O(klog(n))
總結(jié)與展望
本文主要介紹了一種可合并堆——二項堆剑逃。首先將其和二進制加法進行了類比浙宜，然后引出其基本實現(xiàn)元素——二項樹，并利用二項樹構(gòu)成二項堆蛹磺。然后本文大致介紹了其代碼實現(xiàn)粟瞬，同時指出了其在面臨邊界特殊情形時操作時間復(fù)雜度變差的理由。
為了規(guī)避這一風(fēng)險萤捆，我們后面將介紹 lazy 二項堆裙品。
同時二項堆仍沒有解決decrease key難題，后面將介紹斐波那契堆俗或。
如果覺得這種可合并堆實現(xiàn)比較復(fù)雜市怎，那么后面介紹的左傾堆實現(xiàn)起來就很簡單啦。
Acknowledgement
本文大部分動圖都來自Keith Schwarz@Stanford辛慰，向其表示感謝区匠！
