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.
78 lines
2.8 KiB
C++
78 lines
2.8 KiB
C++
BinomialQueue.h - Header file for binomial queue
|
|
|
|
#ifndef BINOMIAL_QUEUE_H_
|
|
#define BINOMIAL_QUEUE_H_
|
|
|
|
#include <iostream.h>
|
|
#include "vector.h"
|
|
|
|
// Binomial queue class
|
|
//
|
|
// CONSTRUCTION: with no parameters
|
|
//
|
|
// ******************PUBLIC OPERATIONS*********************
|
|
// void insert( x ) --> Insert x
|
|
// deleteMin( ) --> Return and remove 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 BinomialQueue;
|
|
|
|
template <class Comparable>
|
|
class BinomialNode
|
|
{
|
|
Comparable element;
|
|
BinomialNode *leftChild;
|
|
BinomialNode *nextSibling;
|
|
|
|
BinomialNode( const Comparable & theElement,
|
|
BinomialNode *lt, BinomialNode *rt )
|
|
: element( theElement ), leftChild( lt ), nextSibling( rt ) { }
|
|
friend class BinomialQueue<Comparable>;
|
|
};
|
|
|
|
template <class Comparable>
|
|
class BinomialQueue
|
|
{
|
|
public:
|
|
BinomialQueue( );
|
|
BinomialQueue( const BinomialQueue & rhs );
|
|
~BinomialQueue( );
|
|
|
|
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( BinomialQueue & rhs );
|
|
|
|
const BinomialQueue & operator=( const BinomialQueue & rhs );
|
|
|
|
private:
|
|
int currentSize; // Number of items in the priority queue
|
|
vector<BinomialNode<Comparable> *> theTrees; // An array of tree roots
|
|
|
|
int findMinIndex( ) const;
|
|
int capacity( ) const;
|
|
BinomialNode<Comparable> * combineTrees( BinomialNode<Comparable> *t1,
|
|
BinomialNode<Comparable> *t2 ) const;
|
|
void makeEmpty( BinomialNode<Comparable> * & t ) const;
|
|
BinomialNode<Comparable> * clone( BinomialNode<Comparable> * t ) const;
|
|
};
|
|
|
|
#include "BinomialQueue.cpp"
|
|
#endif
|