【转】作式堆分析和实现

只看该作者 · 2017-1-5 12:29

介绍：

定义：

左式堆（Leftist Heaps)又称作最左堆、左倾堆，是计算机语言中较为常用的一个数据结构。左式堆作为堆的一种，保留了堆的一些属性。第1，左式堆仍然以二叉树的形式构建；第2，左式堆的任意结点的值比其子树任意结点值均小（最小堆的特性）。但和一般的二叉堆不同，左式堆不再是一棵完全二叉树（Complete tree)，而且是一棵极不平衡的树。

那么为什么要使用左式堆，左式堆同样是优先队列，并且实现的时候使用了指针，不支持直接访问元素。看起来效果与二叉堆相同，并且实现变得复杂了。使用指针，既可以是缺点，同样也可以是优点。有了指针之后，就可以支持合并操作了。使用左式堆的目的就是为了能够支持合并优先队列。

左式堆的特性：

零路径长：从X到一个不具有两个儿子的结点的最短路径的长。

1. 任一结点的零路径长比他的诸儿子结点的零路径长的最小值多1

2. 父节点属性值小于子节点属性值；

3. 堆中的任何节点，其左儿子的零路径长>=右儿子的零路径长的二叉树。

左式堆的复杂度

左式堆的操作都是基于合并，而合并仅对右路做合并，而右路结点的数量为总数量的对数关系，所以左式堆的三个操作（合并，删除，插入）所花的时间为O(logN).

基本操作：
合并：

左式堆的合并操作基于递归完成，算法如下：

1.如果有一棵树是空树，则返回另一棵树；否则递归地合并根结点较小的堆的右子树和根结点较大的堆。
2.使形成的新堆作为较小堆的右子树。
3.如果违反了左式堆的特性，交换两个子树的位置。
4.更新Npl。

删除最小值/最大值：

删除操作的做法相当的简单，删除左式堆的根节点，合并左右子树即可。

插入：

将需要插入的节点当做一棵左式堆树，进行合并即可。

编码实现：

左式堆定义：

左式堆的实现依赖指针，那么首先是与基础的二叉树相同。因为需要维护Npl值，所以每个节点里需要添加Npl。

.h文件定义如下：

[cpp] view plain copy

#ifndef _LEFTIST_HEAP
#define _LEFTIST_HEAP
struct TreeNode;
typedef TreeNode * PriorityQueue;
typedef int ElementType;
PriorityQueue merge(PriorityQueue H1, PriorityQueue H2);
ElementType findMin(PriorityQueue H);
int isEmpty(PriorityQueue H);
PriorityQueue deleteMin(PriorityQueue H);
PriorityQueue insert(ElementType X, PriorityQueue H);
void PrintTree(PriorityQueue T);
void PrintTree(PriorityQueue T, int depth);
void PrintDepth(ElementType A, int depth);
#endif
struct TreeNode
{
ElementType Element;
PriorityQueue Left;
PriorityQueue Right;
int Npl;
};

[cpp] view plain copy

#ifndef _LEFTIST_HEAP
#define _LEFTIST_HEAP
struct TreeNode;
typedef TreeNode * PriorityQueue;
typedef int ElementType;
PriorityQueue merge(PriorityQueue H1, PriorityQueue H2);
ElementType findMin(PriorityQueue H);
int isEmpty(PriorityQueue H);
PriorityQueue deleteMin(PriorityQueue H);
PriorityQueue insert(ElementType X, PriorityQueue H);
void PrintTree(PriorityQueue T);
void PrintTree(PriorityQueue T, int depth);
void PrintDepth(ElementType A, int depth);
#endif
struct TreeNode
{
ElementType Element;
PriorityQueue Left;
PriorityQueue Right;
int Npl;
};

合并操作：

合并操作的基本方式就如上算法所描述，可以使用递归的方式也可以使用非递归的方式。在这里我使用递归的方式实现。

[cpp] view plain copy

PriorityQueue merge(PriorityQueue H1, PriorityQueue H2)
{
if(H1 == NULL)
return H2;
if(H2 == NULL)
return H1;
if(H1->Element < H2->Element)
return merge1(H1, H2);
else
return merge1(H2, H1);
}
PriorityQueue merge1(PriorityQueue H1, PriorityQueue H2)
{
if(H1->Left == NULL)
H1->Left = H2;
else
{
H1->Right = merge(H1->Right, H2);
if(H1->Left->Npl < H1->Right->Npl)
switchChildren(H1);
H1->Npl = H1->Right->Npl +1;
}
return H1;
}

[cpp] view plain copy

PriorityQueue merge(PriorityQueue H1, PriorityQueue H2)
{
if(H1 == NULL)
return H2;
if(H2 == NULL)
return H1;
if(H1->Element < H2->Element)
return merge1(H1, H2);
else
return merge1(H2, H1);
}
PriorityQueue merge1(PriorityQueue H1, PriorityQueue H2)
{
if(H1->Left == NULL)
H1->Left = H2;
else
{
H1->Right = merge(H1->Right, H2);
if(H1->Left->Npl < H1->Right->Npl)
switchChildren(H1);
H1->Npl = H1->Right->Npl +1;
}
return H1;
}

总结：

左式堆的实现还是相当的容易，只有合并操作的地方需要稍微花点功夫理解就行了。在左式堆的基础上还可以实现斜堆。只需要去除Npl值，并且在每次合并之后交互左右孩子即可（不保证左式堆性质）。斜堆的实现与左式堆基本相同，在这里就不赘述了。

【转】作式堆分析和实现

相关帖子