首先声明，我的代码基本是照着www.cnblogs.com/skywang12345/p/3638342.html打的，感谢分享。

不过我的疑问是在实现merge时提供的形参为何要加引用，一开始傻乎乎地觉得这样才能真正改动内部指针成员，知道去掉引用run了一把才知道不加引用也能实现合并，加引用除了减少拷贝指针的开销其实没有其他好处了，当然只是我个人的想法，望轻喷。传值调用也能改变内部指针指向的原因是这两条语句，mRoot=rhs->mRoot;x->right=merge(x->right,y);

虽然改变的是局部指针的指向，但由于又进行了一次赋值操作，所以实参pointer也被改变了指向。相当于创建两个局部指针作为实参的拷贝，merge后形成一颗新的左偏树再传给实参。虽然cppprimer还没看到后面，也通过上面的博客大概知道了用法，再表感激。下面贴自己搬运后略微修改的代码：

1 #include 
     
        2 #include 
      
         3   4 using namespace std;  5   6 template 
       
          7 class LeftistNode {  8 public:  9     T key; 10     int npl; 11     LeftistNode* left; 12     LeftistNode* right; 13  14     LeftistNode(T value = -1, LeftistNode* l = 0, LeftistNode* r = 0) ://key值默认为-1 15         key(value), left(l), right(r), npl(0) {} 16 }; 17  18 template 
        
          19 class LeftistHeap { 20 private: 21     LeftistNode
         
           *mRoot; 22 public: 23     //构造函数 24     LeftistHeap() :mRoot(0) {} 25     ~LeftistHeap();//析构函数 26  27     void preOrder();//前序遍历“左倾堆” 28  29     void merge(LeftistHeap
          
           * other);//将自己与other堆合并 30 void insert(T key); 31 void remove();//只支持删除堆顶 32 void destroy(); 33 // 打印左倾堆 34 void print(); 35 36 private: 37 void preOrder(LeftistNode
           
            * heap)const; 38 //如果不解引用指针与其他类型的swap无区别 39 void swapNode(LeftistNode
            
             * &x, LeftistNode
             
              * &y); 40 LeftistNode
              
               * merge(LeftistNode
               
                * x, LeftistNode
                
                 * y); 41 LeftistNode
                 
                  * insert(LeftistNode
                  
                   * heap, T key); 42 LeftistNode
                   
                    * remove(LeftistNode
                    
                     * heap); 43 44 void destroy(LeftistNode
                     
                      * heap); 45 // 打印左倾堆 46 void print(LeftistNode
                      
                       * heap, T key, int direction); 47 }; 48 49 template
                       
                         50 LeftistHeap
                        
                         ::~LeftistHeap() { destroy(); } 51 52 template
                         
                           53 void LeftistHeap
                          
                           ::preOrder(LeftistNode
                           
                            * heap)const { 54 if (heap) { 55 cout << heap->key << endl; 56 preOrder(heap->left); 57 preOrder(heap->right); 58 } 59 } 60 61 template
                            
                              62 void LeftistHeap
                             
                              ::preOrder() { 63 preOrder(mRoot); 64 } 65 66 template
                              
                                67 void LeftistHeap
                               
                                ::swapNode(LeftistNode
                                
                                 * &x, LeftistNode
                                 
                                  * &y) { 68 LeftistNode
                                  
                                   * tmp = x; 69 x = y; 70 y = tmp; 71 } 72 73 template 
                                   
                                     74 LeftistNode
                                    
                                     * LeftistHeap
                                     
                                      ::merge(LeftistNode
                                      
                                       * x, LeftistNode
                                       
                                        * y) { 75 if (x == NULL)return y; 76 if (y == NULL)return x; 77 78 if (x->key > y->key)swapNode(x, y); 79 x->right = merge(x->right, y); 80 81 if (x->left == 0 || x->left->npl < x->right->npl)swapNode(x->left, x->right);//保证左偏 82 83 if (x->right == 0)x->npl = 0; 84 else x->npl = x->right->npl + 1; 85 86 return x; 87 } 88 89 template
                                        
                                          90 void LeftistHeap
                                         
                                          ::merge(LeftistHeap
                                          
                                           *rhs) { 91 mRoot = merge(mRoot, rhs->mRoot);// 92 } 93 94 template
                                           
                                             95 LeftistNode
                                            
                                             * LeftistHeap
                                             
                                              ::insert(LeftistNode
                                              
                                               * heap, T key) { 96 LeftistNode
                                               
                                                * node = new LeftistNode
                                                
                                                 (key, 0, 0); 97 if (node == 0) { 98 cout << "create node failed!" << endl; 99 return heap;100 }101 102 return merge(heap, node);103 }104 105 template 
                                                 
                                                  106 void LeftistHeap
                                                  
                                                   ::insert(T key) {107 mRoot = insert(mRoot, key);108 }109 110 template
                                                   
                                                    111 LeftistNode
                                                    
                                                     * LeftistHeap
                                                     
                                                      ::remove(LeftistNode
                                                      
                                                       * heap) {112 LeftistNode
                                                       
                                                        * l = heap->left;113 LeftistNode
                                                        
                                                         * r = heap->right;114 115 delete heap;116 //heap = 0;//置空117 return merge(l, r);118 }119 120 template
                                                         
                                                          121 void LeftistHeap
                                                          
                                                           ::remove() { mRoot = remove(mRoot); }122 123 template
                                                           
                                                            124 void LeftistHeap
                                                            
                                                             ::destroy(LeftistNode
                                                             
                                                              * heap) {125 if (heap == 0)return;126 127 destroy(heap->left);128 destroy(heap->right);129 130 delete heap;131 }132 133 template 
                                                              
                                                               134 void LeftistHeap
                                                               
                                                                ::print(LeftistNode
                                                                
                                                                 * heap, T key, int direction)135 {136 if (heap != NULL)137 {138 if (direction == 0) // heap是根节点139 cout << setw(2) << heap->key << "(" << heap->npl << ") is root" << endl;140 else // heap是分支节点141 cout << setw(2) << heap->key << "(" << heap->npl << ") is " << setw(2) << key << "'s " << setw(12) << (direction == 1 ? "right child" : "left child") << endl;142 143 print(heap->left, heap->key, -1);144 print(heap->right, heap->key, 1);145 }146 }147 148 template 
                                                                 
                                                                  149 void LeftistHeap
                                                                  
                                                                   ::print()150 {151 if (mRoot != NULL)152 print(mRoot, mRoot->key, 0);153 }154 155 156 template
                                                                   
                                                                    157 void LeftistHeap
                                                                    
                                                                     ::destroy() { destroy(mRoot); }158 159 int main(void) {160 int i;161 int a[] = { 10,40,24,30,36,20,12,16 };162 int b[] = { 17,13,11,15,19,21,23 };163 int alen = sizeof(a) / sizeof(a[0]);164 int blen = sizeof(b) / sizeof(b[0]);165 LeftistHeap
                                                                     
                                                                      * ha = new LeftistHeap
                                                                      
                                                                       ();166 LeftistHeap
                                                                       
                                                                        * hb = new LeftistHeap
                                                                        
                                                                         ();167 168 cout << "== 左倾堆(ha)中依次添加: ";169 for (i = 0; i
                                                                         
                                                                          insert(a[i]);173 }174 cout << "\n== 左倾堆(ha)的详细信息: " << endl;175 ha->print();176 177 178 cout << "\n== 左倾堆(hb)中依次添加: ";179 for (i = 0; i
                                                                          
                                                                           insert(b[i]);183 }184 cout << "\n== 左倾堆(hb)的详细信息: " << endl;185 hb->print();186 187 188 // 将"左倾堆hb"合并到"左倾堆ha"中。189 ha->merge(hb);190 cout << "\n== 合并ha和hb后的详细信息: " << endl;191 ha->print();192 193 194 // 销毁195 ha->destroy();196 197 return 0;198 199 }