概要
上一章介绍了斜堆的基本概念，并通过C语言实现了斜堆。本章是斜堆的C++实现。
目录
1. 斜堆的介绍
2. 斜堆的基本操作
3. 斜堆的C++实现(完整源码)
4. 斜堆的C++测试程序
转载请注明出处：http://www.cnblogs.com/skywang12345/p/3638524.html
更多内容：数据结构与算法系列 目录
斜堆的介绍
斜堆(Skew
heap)也叫自适应堆(self-adjusting
heap)，它是左倾堆的一个变种。和左倾堆一样，它通常也用于实现优先队列；作为一种自适应的左倾堆，它的合并操作的时间复杂度也是O(lg
n)。
它与左倾堆的差别是：
(01)
斜堆的节点没有"零距离"这个属性，而左倾堆则有。
(02)
斜堆的合并操作和左倾堆的合并操作算法不同。
斜堆的合并操作
(01)
如果一个空斜堆与一个非空斜堆合并，返回非空斜堆。
(02)
如果两个斜堆都非空，那么比较两个根节点，取较小堆的根节点为新的根节点。将"较小堆的根节点的右孩子"和"较大堆"进行合并。
(03)
合并后，交换新堆根节点的左孩子和右孩子。
第(03)步是斜堆和左倾堆的合并操作差别的关键所在，如果是左倾堆，则合并后要比较左右孩子的零距离大小，若右孩子的零距离
> 左孩子的零距离，则交换左右孩子；最后，在设置根的零距离。
斜堆的基本操作
1. 基本定义
template <class T> class SkewNode{ public: T key; // 关键字(键值) SkewNode *left; // 左孩子 SkewNode *right; // 右孩子 SkewNode(T value, SkewNode *l, SkewNode *r): key(value), left(l),right(r) {} };
SkewNode是斜堆对应的节点类。
template <class T> class SkewHeap { private: SkewNode<T> *mRoot; // 根结点 public: SkewHeap(); ~SkewHeap(); // 前序遍历"斜堆" void preOrder(); // 中序遍历"斜堆" void inOrder(); // 后序遍历"斜堆" void postOrder(); // 将other的斜堆合并到this中。 void merge(SkewHeap<T>* other); // 将结点(key为节点键值)插入到斜堆中 void insert(T key); // 删除结点(key为节点键值) void remove(); // 销毁斜堆 void destroy(); // 打印斜堆 void print(); private: // 前序遍历"斜堆" void preOrder(SkewNode<T>* heap) const; // 中序遍历"斜堆" void inOrder(SkewNode<T>* heap) const; // 后序遍历"斜堆" void postOrder(SkewNode<T>* heap) const; // 交换节点x和节点y void swapNode(SkewNode<T> *&x, SkewNode<T> *&y); // 合并"斜堆x"和"斜堆y" SkewNode<T>* merge(SkewNode<T>* &x, SkewNode<T>* &y); // 销毁斜堆 void destroy(SkewNode<T>* &heap); // 打印斜堆 void print(SkewNode<T>* heap, T key, int direction); };
SkewHeap是斜堆类，它包含了斜堆的根节点，以及斜堆的操作。
2. 合并
/* * 合并"斜堆x"和"斜堆y" */ template <class T> SkewNode<T>* SkewHeap<T>::merge(SkewNode<T>* &x, SkewNode<T>* &y) { if(x == NULL) return y; if(y == NULL) return x; // 合并x和y时，将x作为合并后的树的根； // 这里的操作是保证: x的key < y的key if(x->key > y->key) swapNode(x, y); // 将x的右孩子和y合并， // 合并后直接交换x的左右孩子，而不需要像左倾堆一样考虑它们的npl。 SkewNode<T> *tmp = merge(x->right, y); x->right = x->left; x->left = tmp; return x; } /* * 将other的斜堆合并到this中。 */ template <class T> void SkewHeap<T>::merge(SkewHeap<T>* other) { mRoot = merge(mRoot, other->mRoot); }
merge(x,
y)是内部接口，作用是合并x和y这两个斜堆，并返回得到的新堆的根节点。
merge(other)是外部接口，作用是将other合并到当前堆中。
3.
添加
/* * 新建键值为key的结点并将其插入到斜堆中 * * 参数说明： * heap 斜堆的根结点 * key 插入的结点的键值 * 返回值： * 根节点 */ template <class T> void SkewHeap<T>::insert(T key) { SkewNode<T> *node; // 新建结点 // 新建节点 node = new SkewNode<T>(key, NULL, NULL); if (node==NULL) { cout << "ERROR: create node failed!" << endl; return ; } mRoot = merge(mRoot, node); }
insert(key)的作用是新建键值为key的节点，并将其加入到当前斜堆中。
4. 删除
/* * 删除结点 */ template <class T> void SkewHeap<T>::remove() { if (mRoot == NULL) return NULL; SkewNode<T> *l = mRoot->left; SkewNode<T> *r = mRoot->right; // 删除根节点 delete mRoot; // 左右子树合并后的新树 mRoot = merge(l, r); }
remove()的作用是删除斜堆的最小节点。
注意：关于斜堆的"前序遍历"、"中序遍历"、"后序遍历"、"打印"、"销毁"等接口就不再单独介绍了。后文的源码中有给出它们的实现代码，Please RTFSC(Read The Fucking Source Code)！
斜堆的C++实现(完整源码)
斜堆的实现文件(SkewHeap.h)
1 /** 2 * C++: 斜堆 3 * 4 * @author skywang 5 * @date 2014/03/31 6 */ 7 8 #ifndef _SKEW_HEAP_HPP_ 9 #define _SKEW_HEAP_HPP_ 10 11 #include <iomanip> 12 #include <iostream> 13 using namespace std; 14 15 template <class T> 16 class SkewNode{ 17 public: 18 T key; // 关键字(键值) 19 SkewNode *left; // 左孩子 20 SkewNode *right; // 右孩子 21 22 SkewNode(T value, SkewNode *l, SkewNode *r): 23 key(value), left(l),right(r) {} 24 }; 25 26 template <class T> 27 class SkewHeap { 28 private: 29 SkewNode<T> *mRoot; // 根结点 30 31 public: 32 SkewHeap(); 33 ~SkewHeap(); 34 35 // 前序遍历"斜堆" 36 void preOrder(); 37 // 中序遍历"斜堆" 38 void inOrder(); 39 // 后序遍历"斜堆" 40 void postOrder(); 41 42 // 将other的斜堆合并到this中。 43 void merge(SkewHeap<T>* other); 44 // 将结点(key为节点键值)插入到斜堆中 45 void insert(T key); 46 // 删除结点(key为节点键值) 47 void remove(); 48 49 // 销毁斜堆 50 void destroy(); 51 52 // 打印斜堆 53 void print(); 54 private: 55 56 // 前序遍历"斜堆" 57 void preOrder(SkewNode<T>* heap) const; 58 // 中序遍历"斜堆" 59 void inOrder(SkewNode<T>* heap) const; 60 // 后序遍历"斜堆" 61 void postOrder(SkewNode<T>* heap) const; 62 63 // 交换节点x和节点y 64 void swapNode(SkewNode<T> *&x, SkewNode<T> *&y); 65 // 合并"斜堆x"和"斜堆y" 66 SkewNode<T>* merge(SkewNode<T>* &x, SkewNode<T>* &y); 67 68 // 销毁斜堆 69 void destroy(SkewNode<T>* &heap); 70 71 // 打印斜堆 72 void print(SkewNode<T>* heap, T key, int direction); 73 }; 74 75 /* 76 * 构造函数 77 */ 78 template <class T> 79 SkewHeap<T>::SkewHeap():mRoot(NULL) 80 { 81 } 82 83 /* 84 * 析构函数 85 */ 86 template <class T> 87 SkewHeap<T>::~SkewHeap() 88 { 89 destroy(mRoot); 90 } 91 92 /* 93 * 前序遍历"斜堆" 94 */ 95 template <class T> 96 void SkewHeap<T>::preOrder(SkewNode<T>* heap) const 97 { 98 if(heap != NULL) 99 { 100 cout<< heap->key << " " ; 101 preOrder(heap->left); 102 preOrder(heap->right); 103 } 104 } 105 106 template <class T> 107 void SkewHeap<T>::preOrder() 108 { 109 preOrder(mRoot); 110 } 111 112 /* 113 * 中序遍历"斜堆" 114 */ 115 template <class T> 116 void SkewHeap<T>::inOrder(SkewNode<T>* heap) const 117 { 118 if(heap != NULL) 119 { 120 inOrder(heap->left); 121 cout<< heap->key << " " ; 122 inOrder(heap->right); 123 } 124 } 125 126 template <class T> 127 void SkewHeap<T>::inOrder() 128 { 129 inOrder(mRoot); 130 } 131 132 /* 133 * 后序遍历"斜堆" 134 */ 135 template <class T> 136 void SkewHeap<T>::postOrder(SkewNode<T>* heap) const 137 { 138 if(heap != NULL) 139 { 140 postOrder(heap->left); 141 postOrder(heap->right); 142 cout<< heap->key << " " ; 143 } 144 } 145 146 template <class T> 147 void SkewHeap<T>::postOrder() 148 { 149 postOrder(mRoot); 150 } 151 152 /* 153 * 交换两个节点的内容 154 */ 155 template <class T> 156 void SkewHeap<T>::swapNode(SkewNode<T> *&x, SkewNode<T> *&y) 157 { 158 SkewNode<T> *tmp = x; 159 x = y; 160 y = tmp; 161 } 162 163 164 /* 165 * 合并"斜堆x"和"斜堆y" 166 */ 167 template <class T> 168 SkewNode<T>* SkewHeap<T>::merge(SkewNode<T>* &x, SkewNode<T>* &y) 169 { 170 if(x == NULL) 171 return y; 172 if(y == NULL) 173 return x; 174 175 // 合并x和y时，将x作为合并后的树的根； 176 // 这里的操作是保证: x的key < y的key 177 if(x->key > y->key) 178 swapNode(x, y); 179 180 // 将x的右孩子和y合并， 181 // 合并后直接交换x的左右孩子，而不需要像左倾堆一样考虑它们的npl。 182 SkewNode<T> *tmp = merge(x->right, y); 183 x->right = x->left; 184 x->left = tmp; 185 186 return x; 187 } 188 189 /* 190 * 将other的斜堆合并到this中。 191 */ 192 template <class T> 193 void SkewHeap<T>::merge(SkewHeap<T>* other) 194 { 195 mRoot = merge(mRoot, other->mRoot); 196 } 197 198 /* 199 * 新建键值为key的结点并将其插入到斜堆中 200 * 201 * 参数说明： 202 * heap 斜堆的根结点 203 * key 插入的结点的键值 204 * 返回值： 205 * 根节点 206 */ 207 template <class T> 208 void SkewHeap<T>::insert(T key) 209 { 210 SkewNode<T> *node; // 新建结点 211 212 // 新建节点 213 node = new SkewNode<T>(key, NULL, NULL); 214 if (node==NULL) 215 { 216 cout << "ERROR: create node failed!" << endl; 217 return ; 218 } 219 220 mRoot = merge(mRoot, node); 221 } 222 223 /* 224 * 删除结点 225 */ 226 template <class T> 227 void SkewHeap<T>::remove() 228 { 229 if (mRoot == NULL) 230 return NULL; 231 232 SkewNode<T> *l = mRoot->left; 233 SkewNode<T> *r = mRoot->right; 234 235 // 删除根节点 236 delete mRoot; 237 // 左右子树合并后的新树 238 mRoot = merge(l, r); 239 } 240 241 /* 242 * 销毁斜堆 243 */ 244 template <class T> 245 void SkewHeap<T>::destroy(SkewNode<T>* &heap) 246 { 247 if (heap==NULL) 248 return ; 249 250 if (heap->left != NULL) 251 destroy(heap->left); 252 if (heap->right != NULL) 253 destroy(heap->right); 254 255 delete heap; 256 } 257 258 template <class T> 259 void SkewHeap<T>::destroy() 260 { 261 destroy(mRoot); 262 } 263 264 /* 265 * 打印"斜堆" 266 * 267 * key -- 节点的键值 268 * direction -- 0，表示该节点是根节点; 269 * -1，表示该节点是它的父结点的左孩子; 270 * 1，表示该节点是它的父结点的右孩子。 271 */ 272 template <class T> 273 void SkewHeap<T>::print(SkewNode<T>* heap, T key, int direction) 274 { 275 if(heap != NULL) 276 { 277 if(direction==0) // heap是根节点 278 cout << setw(2) << heap->key << " is root" << endl; 279 else // heap是分支节点 280 cout << setw(2) << heap->key << " is " << setw(2) << key << "‘s " << setw(12) << (direction==1?"right child" : "left child") << endl; 281 282 print(heap->left, heap->key, -1); 283 print(heap->right,heap->key, 1); 284 } 285 } 286 287 template <class T> 288 void SkewHeap<T>::print() 289 { 290 if (mRoot != NULL) 291 print(mRoot, mRoot->key, 0); 292 } 293 #endif
斜堆的测试程序(SkewHeapTest.cpp)
1 /** 2 * C 语言: 斜堆 3 * 4 * @author skywang 5 * @date 2014/03/31 6 */ 7 8 #include <iostream> 9 #include "SkewHeap.h" 10 using namespace std; 11 12 int main() 13 { 14 int i; 15 int a[]= {10,40,24,30,36,20,12,16}; 16 int b[]= {17,13,11,15,19,21,23}; 17 int alen=sizeof(a)/sizeof(a[0]); 18 int blen=sizeof(b)/sizeof(b[0]); 19 SkewHeap<int>* ha=new SkewHeap<int>(); 20 SkewHeap<int>* hb=new SkewHeap<int>(); 21 22 cout << "== 斜堆(ha)中依次添加: "; 23 for(i=0; i<alen; i++) 24 { 25 cout << a[i] <<" "; 26 ha->insert(a[i]); 27 } 28 cout << "\n== 斜堆(ha)的详细信息: " << endl; 29 ha->print(); 30 31 32 cout << "\n== 斜堆(hb)中依次添加: "; 33 for(i=0; i<blen; i++) 34 { 35 cout << b[i] <<" "; 36 hb->insert(b[i]); 37 } 38 cout << "\n== 斜堆(hb)的详细信息: " << endl; 39 hb->print(); 40 41 42 // 将"斜堆hb"合并到"斜堆ha"中。 43 ha->merge(hb); 44 cout << "\n== 合并ha和hb后的详细信息: " << endl; 45 ha->print(); 46 47 48 // 销毁 49 ha->destroy(); 50 51 return 0; 52 }
斜堆的C++测试程序
斜堆的测试程序已经包含在它的实现文件(SkewHeapTest.cpp)中了，这里仅给出它的运行结果：
== 斜堆(ha)中依次添加: 10 40 24 30 36 20 12 16 == 斜堆(ha)的详细信息: 10 is root 16 is 10‘s left child 20 is 16‘s left child 30 is 20‘s left child 40 is 30‘s left child 12 is 10‘s right child 24 is 12‘s left child 36 is 24‘s left child == 斜堆(hb)中依次添加: 17 13 11 15 19 21 23 == 斜堆(hb)的详细信息: 11 is root 13 is 11‘s left child 17 is 13‘s left child 23 is 17‘s left child 19 is 13‘s right child 15 is 11‘s right child 21 is 15‘s left child == 合并ha和hb后的详细信息: 10 is root 11 is 10‘s left child 12 is 11‘s left child 15 is 12‘s left child 21 is 15‘s left child 24 is 12‘s right child 36 is 24‘s left child 13 is 11‘s right child 17 is 13‘s left child 23 is 17‘s left child 19 is 13‘s right child 16 is 10‘s right child 20 is 16‘s left child 30 is 20‘s left child 40 is 30‘s left child