1 #ifndef LEFTIST_HEAP_H  2 #define LEFTIST_HEAP_H  3   4 #include "dsexceptions.h"  5 #include <iostream>  6 using namespace std;  7   8 // Leftist heap class  9 // 10 // CONSTRUCTION: with no parameters 11 // 12 // ******************PUBLIC OPERATIONS********************* 13 // void insert( x )       --> Insert x 14 // deleteMin( minItem )   --> Remove (and optionally return) smallest item 15 // Comparable findMin( )  --> Return smallest item 16 // bool isEmpty( )        --> Return true if empty; else false 17 // void makeEmpty( )      --> Remove all items 18 // void merge( rhs )      --> Absorb rhs into this heap 19 // ******************ERRORS******************************** 20 // Throws UnderflowException as warranted 21  22 template <typename Comparable> 23 class LeftistHeap 24 { 25   public: 26     LeftistHeap( ) : root{ nullptr } 27       { } 28     LeftistHeap( const LeftistHeap & rhs ) : root{ nullptr } 29       { root = clone( rhs.root ); } 30      31     LeftistHeap( LeftistHeap && rhs ) : root{ rhs.root } 32     { 33         rhs.root = nullptr; 34     } 35      36     ~LeftistHeap( ) 37       { makeEmpty( ); } 38      39      40     /** 41      * Deep copy. 42      */ 43     LeftistHeap & operator=( const LeftistHeap & rhs ) 44     { 45         LeftistHeap copy = rhs; 46         std::swap( *this, copy ); 47         return *this; 48     } 49          50     /** 51      * Move. 52      */ 53     LeftistHeap & operator=( LeftistHeap && rhs ) 54     { 55         std::swap( root, rhs.root ); 56          57         return *this; 58     } 59      60     /** 61      * Returns true if empty, false otherwise. 62      */ 63     bool isEmpty( ) const 64       { return root == nullptr; } 65      66     /** 67      * Find the smallest item in the priority queue. 68      * Return the smallest item, or throw Underflow if empty. 69      */ 70     const Comparable & findMin( ) const 71     { 72         if( isEmpty( ) ) 73             throw UnderflowException{ }; 74         return root->element; 75     } 76  77     /** 78      * Inserts x; duplicates allowed. 79      */ 80     void insert( const Comparable & x ) 81       { root = merge( new LeftistNode{ x }, root ); } 82  83     /** 84      * Inserts x; duplicates allowed. 85      */ 86     void insert( Comparable && x ) 87       { root = merge( new LeftistNode{ std::move( x ) }, root ); } 88  89     /** 90      * Remove the minimum item. 91      * Throws UnderflowException if empty. 92      */ 93     void deleteMin( ) 94     { 95         if( isEmpty( ) ) 96             throw UnderflowException{ }; 97  98         LeftistNode *oldRoot = root; 99         root = merge( root->left, root->right );100         delete oldRoot;101     }102 103     /**104      * Remove the minimum item and place it in minItem.105      * Throws UnderflowException if empty.106      */107     void deleteMin( Comparable & minItem )108     {109         minItem = findMin( );110         deleteMin( );111     }112 113     /**114      * Make the priority queue logically empty.115      */116     void makeEmpty( )117     {118         reclaimMemory( root );119         root = nullptr;120     }121 122     /**123      * Merge rhs into the priority queue.124      * rhs becomes empty. rhs must be different from this.125      */126     void merge( LeftistHeap & rhs )127     {128         if( this == &rhs )    // Avoid aliasing problems129             return;130 131         root = merge( root, rhs.root );132         rhs.root = nullptr;133     }134 135 136   private:137     struct LeftistNode138     {139         Comparable   element;140         LeftistNode *left;141         LeftistNode *right;142         int          npl;143 144         LeftistNode( const Comparable & e, LeftistNode *lt = nullptr,145                         LeftistNode *rt = nullptr, int np = 0 )146           : element{ e }, left{ lt }, right{ rt }, npl{ np } { }147         148         LeftistNode( Comparable && e, LeftistNode *lt = nullptr,149                         LeftistNode *rt = nullptr, int np = 0 )150           : element{ std::move( e ) }, left{ lt }, right{ rt }, npl{ np } { }151     };152 153     LeftistNode *root;154 155     /**156      * Internal method to merge two roots.157      * Deals with deviant cases and calls recursive merge1.158      */159     LeftistNode * merge( LeftistNode *h1, LeftistNode *h2 )160     {161         if( h1 == nullptr )162             return h2;163         if( h2 == nullptr )164             return h1;165         if( h1->element < h2->element )166             return merge1( h1, h2 );167         else168             return merge1( h2, h1 );169     }170 171     /**172      * Internal method to merge two roots.173      * Assumes trees are not empty, and h1‘s root contains smallest item.174      */175     LeftistNode * merge1( LeftistNode *h1, LeftistNode *h2 )176     {177         if( h1->left == nullptr )   // Single node178             h1->left = h2;       // Other fields in h1 already accurate179         else180         {181             h1->right = merge( h1->right, h2 );182             if( h1->left->npl < h1->right->npl )183                 swapChildren( h1 );184             h1->npl = h1->right->npl + 1;185         }186         return h1;187     }188 189     /**190      * Swaps t‘s two children.191      */192     void swapChildren( LeftistNode *t )193     {194         LeftistNode *tmp = t->left;195         t->left = t->right;196         t->right = tmp;197     }198 199     /**200      * Internal method to make the tree empty.201      * WARNING: This is prone to running out of stack space;202      *          exercises suggest a solution.203      */204     void reclaimMemory( LeftistNode *t )205     {206         if( t != nullptr )207         {208             reclaimMemory( t->left );209             reclaimMemory( t->right );210             delete t;211         }212     }213     214     /**215      * Internal method to clone subtree.216      * WARNING: This is prone to running out of stack space.217      *          exercises suggest a solution.218      */219     LeftistNode * clone( LeftistNode *t ) const220     {221         if( t == nullptr )222             return nullptr;223         else224             return new LeftistNode{ t->element, clone( t->left ), clone( t->right ), t->npl };225     }226 };227 228 #endif

 1 #include "LeftistHeap.h" 2 #include <iostream> 3 using namespace std; 4  5 int main( ) 6 { 7     int numItems = 10000; 8     LeftistHeap<int> h; 9     LeftistHeap<int> h1;10     LeftistHeap<int> h2;11     int i = 37;12 13     cout << "Begin test..." << endl;14     for( i = 37; i != 0; i = ( i + 37 ) % numItems )15         if( i % 2 == 0 )16             h1.insert( i );17         else18             h.insert( i );19     h.merge( h1 );20     h2 = h;21 22     for( i = 1; i < numItems; ++i )23     {24         int x;25         h2.deleteMin( x );26         if( x != i )27             cout << "Oops! " << i << endl;28     }29 30     if( !h1.isEmpty( ) )31         cout << "Oops! h1 should have been empty!" << endl;32 33     cout << "End test... no other output is good" << endl;34 35     return 0;36 }