Instantly share code, notes, and snippets.

Embed
What would you like to do?
Leftist Heap
#ifndef LEFTIST_HEAP_H
#define LEFTIST_HEAP_H
#include "dsexceptions.h"
#include <iostream>
using namespace std;
template <typename Comparable>
class LeftistHeap
{
public:
LeftistHeap( ) : root{ nullptr }
{ }
LeftistHeap( const LeftistHeap & rhs ) : root{ nullptr }
{ root = clone( rhs.root ); }
LeftistHeap( LeftistHeap && rhs ) : root{ rhs.root }
{
rhs.root = nullptr;
}
~LeftistHeap( )
{ makeEmpty( ); }
LeftistHeap & operator=( const LeftistHeap & rhs )
{
LeftistHeap copy = rhs;
std::swap( *this, copy );
return *this;
}
LeftistHeap & operator=( LeftistHeap && rhs )
{
std::swap( root, rhs.root );
return *this;
}
bool isEmpty( ) const
{ return root == nullptr; }
const Comparable & findMin( ) const
{
if( isEmpty( ) )
throw UnderflowException{ };
return root->element;
}
void insert( const Comparable & x )
{ root = merge( new LeftistNode{ x }, root ); }
void insert( Comparable && x )
{ root = merge( new LeftistNode{ std::move( x ) }, root ); }
void deleteMin( )
{
if( isEmpty( ) )
throw UnderflowException{ };
LeftistNode *oldRoot = root;
root = merge( root->left, root->right );
delete oldRoot;
}
void deleteMin( Comparable & minItem )
{
minItem = findMin( );
deleteMin( );
}
void makeEmpty( )
{
reclaimMemory( root );
root = nullptr;
}
void merge( LeftistHeap & rhs )
{
if( this == &rhs ) // Avoid aliasing problems
return;
root = merge( root, rhs.root );
rhs.root = nullptr;
}
private:
struct LeftistNode
{
Comparable element;
LeftistNode *left;
LeftistNode *right;
int npl;
LeftistNode( const Comparable & e, LeftistNode *lt = nullptr,
LeftistNode *rt = nullptr, int np = 0 )
: element{ e }, left{ lt }, right{ rt }, npl{ np } { }
LeftistNode( Comparable && e, LeftistNode *lt = nullptr,
LeftistNode *rt = nullptr, int np = 0 )
: element{ std::move( e ) }, left{ lt }, right{ rt }, npl{ np } { }
};
LeftistNode *root;
LeftistNode * merge( LeftistNode *h1, LeftistNode *h2 )
{
if( h1 == nullptr )
return h2;
if( h2 == nullptr )
return h1;
if( h1->element < h2->element )
return merge1( h1, h2 );
else
return merge1( h2, h1 );
}
LeftistNode * merge1( LeftistNode *h1, LeftistNode *h2 )
{
if( h1->left == nullptr ) // Single node
h1->left = h2; // Other fields in h1 already accurate
else
{
h1->right = merge( h1->right, h2 );
if( h1->left->npl < h1->right->npl )
swapChildren( h1 );
h1->npl = h1->right->npl + 1;
}
return h1;
}
void swapChildren( LeftistNode *t )
{
LeftistNode *tmp = t->left;
t->left = t->right;
t->right = tmp;
}
void reclaimMemory( LeftistNode *t )
{
if( t != nullptr )
{
reclaimMemory( t->left );
reclaimMemory( t->right );
delete t;
}
}
LeftistNode * clone( LeftistNode *t ) const
{
if( t == nullptr )
return nullptr;
else
return new LeftistNode{ t->element, clone( t->left ), clone( t->right ), t->npl };
}
};
#endif
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment