定义:左式堆(Leftist Heaps)又称作最左堆、左倾堆,是计算机语言中较为常用的一个数据结构。左式堆作为堆的一种,保留了堆的一些属性。第1,左式堆仍然以二叉树的形式构建;第2,左式堆的任意结点的值比其子树任意结点值均小(最小堆的特性)。但和一般的二叉堆不同,左式堆不再是一棵完全二叉树(Complete tree),而且是一棵极不平衡的树。
性质:
零路径长:从X到一个不具有两个儿子的结点的最短路径的长。
-
任一结点的零路径长比他的诸儿子结点的零路径长的最小值多1
-
父节点属性值小于子节点属性值;
-
堆中的任何节点,其左儿子的零路径长>=右儿子的零路径长的二叉树。
操作:
左式堆的操作都是基于合并,而合并仅对右路做合并,而右路结点的数量为总数量的对数关系,所以左式堆的三个操作(合并,删除,插入)所花的时间为O(logN).
左式堆的合并操作基于递归完成,算法如下:
1.如果有一棵树是空树,则返回另一棵树;否则递归地合并根结点较小的堆的右子树和根结点较大的堆。
2.使形成的新堆作为较小堆的右子树。
3.如果违反了左式堆的特性,交换两个子树的位置。4.更新Npl。
删除最小值/最大值:
删除操作的做法相当的简单,删除左式堆的根节点,合并左右子树即可。
插入:将需要插入的节点当做一棵左式堆树,进行合并即可。
下面给出左式堆的c++类模板实现
1 #include <iostream>
2 using namespace std;
3
4 template <typename Comparable>
5 class LeftistHeap
6 {
7 public:
8 LeftistHeap() :root(NULL){}
9 LeftistHeap(const LeftistHeap &rhs)
10 {
11 *this = rhs;
12 }
13 ~LeftistHeap()
14 {
15 MakeEmpty();
16 }
17
18 bool IsEmpty() const;
19 const Comparable &FindMin() const;
20
21 void Insert(const Comparable &x);
22 void DeleteMin();
23 void DeleteMin(Comparable &minItem);
24 void MakeEmpty();
25 void Merge(LeftistHeap &rhs);
26
27 const LeftistHeap &operator=(const LeftistHeap &rhs);
28
29 private:
30 struct LeftistNode
31 {
32 Comparable element;
33 LeftistNode *left;
34 LeftistNode *right;
35 int npl;
36
37 LeftistNode(const Comparable &theElement, LeftistNode *lt = NULL, LeftistNode *rt = NULL, int np = 0) :
38 element(theElement), left(lt), right(rt), npl(np){}
39 };
40 LeftistNode *root;
41
42 LeftistNode *Merge(LeftistNode *h1, LeftistNode *h2);
43 LeftistNode *Merge1(LeftistNode *h1, LeftistNode *h2);
44
45 void SwapChildren(LeftistNode *t);
46 void ReclaimMemory(LeftistNode *t);
47 LeftistNode *Clone(LeftistNode *t) const
48 {
49 if (t == NULL)
50 return NULL;
51 else
52 return new LeftistNode(t->element, clone(t->left), clone(t->right));
53 }
54
55 };
56
57
58
59 template <typename Comparable>
60 bool LeftistHeap<Comparable>::IsEmpty() const
61 {
62 return root == NULL;
63 }
64
65 template <typename Comparable>
66 void LeftistHeap<Comparable>::Insert(const Comparable &x)
67 {
68 root = Merge(new LeftistNode(x), root);
69 }
70
71 template <typename Comparable>
72 void LeftistHeap<Comparable>::Merge(LeftistHeap &rhs)
73 {
74 if (this == &rhs)//避免和自己合并
75 return;
76 root = Merge(root, rhs.root);
77 rhs.root = NULL;
78 }
79
80 template <typename Comparable>
81 void LeftistHeap<Comparable>::SwapChildren(LeftistNode *t)
82 {
83 LeftistNode *tmp = t->left;
84 t->left = t->right;
85 t->right = tmp;
86 }
87
88 template <typename Comparable>
89 typename LeftistHeap<Comparable>::LeftistNode *LeftistHeap<Comparable>::Merge1(LeftistNode *h1, LeftistNode *h2)
90 {
91 if (h1->left == NULL)
92 h1->left = h2;
93 else
94 {
95 h1->right = Merge(h1->right, h2);
96 if (h1->left->npl < h1->right->npl)
97 SwapChildren(h1);
98 h1->npl = h1->right->npl + 1;
99 }
100 return h1;
101 }
102
103 template <typename Comparable>
104 typename LeftistHeap<Comparable>::LeftistNode *LeftistHeap<Comparable>::Merge(LeftistNode *h1, LeftistNode *h2)
105 {
106 if (h1 == NULL)
107 return h2;
108 if (h2 == NULL)
109 return h1;
110 if (h1->element < h2->element)
111 return Merge1(h1, h2);
112 else
113 return Merge1(h2, h1);
114 }
115
116
117
118
119
120 template <typename Comparable>
121 void LeftistHeap<Comparable>::DeleteMin()
122 {
123 if (IsEmpty())
124 return;
125 LeftistNode *oldRoot = root;
126 root = Merge(root->left, root->right);
127 delete oldRoot;
128 }
129
130
131 template <typename Comparable>
132 void LeftistHeap<Comparable>::DeleteMin(Comparable &minItem)
133 {
134 minItem = FindMin();
135 DeleteMin();
136 }
137
138 template <typename Comparable>
139 const Comparable & LeftistHeap<Comparable>::FindMin() const
140 {
141 if (!IsEmpty())
142 return root->element;
143 }
144
145
146 template <typename Comparable>
147 void LeftistHeap<Comparable>::ReclaimMemory(LeftistNode *t)
148 {
149 if (t != NULL)
150 {
151 ReclaimMemory(t->left);
152 ReclaimMemory(t->right);
153 delete t;
154 }
155 }
156
157
158 template <typename Comparable>
159 void LeftistHeap<Comparable>::MakeEmpty()
160 {
161 ReclaimMemory(root);
162 root = NULL;
163 }
1 #include "LeftistHeap.h"
2
3
4 int main()
5 {
6 LeftistHeap<int> leftistHeap1, leftistHeap2;
7 int m, n, num;
8 cin >> m;
9 for (int i = 0; i < m; ++i)
10 {
11 cin >> num;
12 leftistHeap1.Insert(num);
13 }
14
15 cin >> n;
16 for (int i = 0; i < n; ++i)
17 {
18 cin >> num;
19 leftistHeap2.Insert(num);
20 }
21
22 leftistHeap1.Merge(leftistHeap2);
23 cout << "min num is " << leftistHeap1.FindMin() << endl;
24 if (leftistHeap1.IsEmpty())
25 {
26 cout << "leftistHeap1 is Empty!" << endl;
27 }
28 else
29 {
30 cout << "leftistHeap1 is not empty!" << endl;
31 }
32
33 int t;
34 while (leftistHeap1.IsEmpty() == false)
35 {
36 leftistHeap1.DeleteMin(t);
37 cout << t << " ";
38 }
39 cout << endl;
40 if (leftistHeap1.IsEmpty())
41 {
42 cout << "leftistHeap1 is empty!" << endl;
43 }
44 else
45 {
46 cout << "leftistHeap1 is not empty!" << endl;
47 }
48
49 }
原文链接: https://www.cnblogs.com/zhangbaochong/p/5243463.html
欢迎关注
微信关注下方公众号,第一时间获取干货硬货;公众号内回复【pdf】免费获取数百本计算机经典书籍
原创文章受到原创版权保护。转载请注明出处:https://www.ccppcoding.com/archives/229591
非原创文章文中已经注明原地址,如有侵权,联系删除
关注公众号【高性能架构探索】,第一时间获取最新文章
转载文章受原作者版权保护。转载请注明原作者出处!