TI

【转】作式堆分析和实现

2019-07-19 14:04发布

站内问答 / TI MCU
5956 0 1770
介绍：定义：

     左式堆（Leftist Heaps)又称作最左堆、左倾堆，是计算机语言中较为常用的一个数据结构。左式堆作为堆的一种，保留了堆的一些属性。第1，左式堆仍然以二叉树的形式构建；第2，左式堆的任意结点的值比其子树任意结点值均小（最小堆的特性）。但和一般的二叉堆不同，左式堆不再是一棵完全二叉树（Complete tree)，而且是一棵极不平衡的树。那么为什么要使用左式堆，左式堆同样是优先队列，并且实现的时候使用了指针，不支持直接访问元素。看起来效果与二叉堆相同，并且实现变得复杂了。使用指针，既可以是缺点，同样也可以是优点。有了指针之后，就可以支持合并操作了。使用左式堆的目的就是为了能够支持合并优先队列。左式堆的特性：
零路径长：从X到一个不具有两个儿子的结点的最短路径的长。1. 任一结点的零路径长比他的诸儿子结点的零路径长的最小值多12. 父节点属性值小于子节点属性值；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值，并且在每次合并之后交互左右孩子即可（不保证左式堆性质）。斜堆的实现与左式堆基本相同，在这里就不赘述了。
发送
 看不清?
0条回答

一周热门 更多>

相关文章