You cannot select more than 25 topics
Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.
77 lines
2.8 KiB
C++
77 lines
2.8 KiB
C++
LeftistHeap.h - Header file for leftist heap
|
|
|
|
#ifndef BINARY_HEAP_H_
|
|
#define BINARY_HEAP_H_
|
|
|
|
#include <iostream.h>
|
|
|
|
// Leftist heap class
|
|
//
|
|
// CONSTRUCTION: with no parameters
|
|
//
|
|
// ******************PUBLIC OPERATIONS*********************
|
|
// void insert( x ) --> Insert x
|
|
// deleteMin( minItem ) --> Remove (and optionally return) smallest item
|
|
// Comparable findMin( ) --> Return smallest item
|
|
// bool isEmpty( ) --> Return true if empty; else false
|
|
// bool isFull( ) --> Return true if full; else false
|
|
// void makeEmpty( ) --> Remove all items
|
|
// void merge( rhs ) --> Absorb rhs into this heap
|
|
// ******************ERRORS********************************
|
|
// Throws Underflow and Overflow as warranted
|
|
|
|
|
|
// Node and forward declaration because g++ does
|
|
// not understand nested classes.
|
|
template <class Comparable>
|
|
class LeftistHeap;
|
|
|
|
template <class Comparable>
|
|
class LeftistNode
|
|
{
|
|
Comparable element;
|
|
LeftistNode *left;
|
|
LeftistNode *right;
|
|
int npl;
|
|
|
|
LeftistNode( const Comparable & theElement, LeftistNode *lt = NULL,
|
|
LeftistNode *rt = NULL, int np = 0 )
|
|
: element( theElement ), left( lt ), right( rt ), npl( np ) { }
|
|
friend class LeftistHeap<Comparable>;
|
|
};
|
|
|
|
template <class Comparable>
|
|
class LeftistHeap
|
|
{
|
|
public:
|
|
LeftistHeap( );
|
|
LeftistHeap( const LeftistHeap & rhs );
|
|
~LeftistHeap( );
|
|
|
|
bool isEmpty( ) const;
|
|
bool isFull( ) const;
|
|
const Comparable & findMin( ) const;
|
|
|
|
void insert( const Comparable & x );
|
|
void deleteMin( );
|
|
void deleteMin( Comparable & minItem );
|
|
void makeEmpty( );
|
|
void merge( LeftistHeap & rhs );
|
|
|
|
const LeftistHeap & operator=( const LeftistHeap & rhs );
|
|
|
|
private:
|
|
LeftistNode<Comparable> *root;
|
|
|
|
LeftistNode<Comparable> * merge( LeftistNode<Comparable> *h1,
|
|
LeftistNode<Comparable> *h2 ) const;
|
|
LeftistNode<Comparable> * merge1( LeftistNode<Comparable> *h1,
|
|
LeftistNode<Comparable> *h2 ) const;
|
|
void swapChildren( LeftistNode<Comparable> * t ) const;
|
|
void reclaimMemory( LeftistNode<Comparable> * t ) const;
|
|
LeftistNode<Comparable> * clone( LeftistNode<Comparable> *t ) const;
|
|
};
|
|
|
|
#include "LeftistHeap.cpp"
|
|
#endif
|