左式堆合并的实现
源自废弃的 csdn blog
//define the leftist heap struct
typedef struct Leftist pLeftist;
struct Leftist{
int element;
pLeftist left, right;
int npl;
};
//build the merged leftist heap and return it
pLeftist BuildHeap(LeftistQueue q){
Leftist h1, h2;
while(!IsEmpty(q)){
h1 = Dequeue(q);
if(IsEmpty(q))
return h1; //the leftist heap has been built
h2 = Dequeue(q);
Enqueue(q, Merge(h1, h2)); //enqueue the new merged leftist heap
}
return NULL; //there is no leftist heap in queue
}
pLeftist Merge(Leftist h1, Leftist h2){
if(!h1)
return h2;
if(!h2)
return h1;
if(h1->element<h2->element) //compare the element and choose the root
return MergeHeap(h1, h2);
else
return MergeHeap(h2, h1);
}
pLeftist MergeHeap(Leftist h1, Leftist h2){
if(!h1->left){
h1->left = h2; //single node
}else{
h1->right = Merge(h1->right, h2);
if(h1->left->npl<h1->right->npl) //make left child's npl >= right's
SwapChl(h1);
h1->npl = h1->right->npl+1; //make the npl equalling its right child+1
}
return h1; //return the root
}
分析
-
左式堆而言，较于小根堆
- 合并速度快，O(n)
- 链表比数组带来更多的开销，并且多一个域(npl)
- 代码相对复杂，其实也不复杂
较于leftist heap,有个skew heap，每次合并都左右换一下，不需要(npl)，如果数据是随机的，也是一个很不错的选择
