/*
* No promises about correctness. Use at your own risk!
*
* Authors:
* Mark Allen Weiss
* Tim Dwyer <tgdwyer@gmail.com>
*
* Copyright (C) 2005 Authors
*
* Released under GNU LGPL. Read the file 'COPYING' for more information.
*/
#ifndef PAIRING_HEAP_H_
#define PAIRING_HEAP_H_
#include <stdlib.h>
#include <fstream>
// Pairing heap class
//
// CONSTRUCTION: with no parameters
//
// ******************PUBLIC OPERATIONS*********************
// PairNode & insert( x ) --> Insert x
// deleteMin( minItem ) --> Remove (and optionally return) smallest item
// T findMin( ) --> Return smallest item
// bool isEmpty( ) --> Return true if empty; else false
// bool isFull( ) --> Return true if empty; else false
// void makeEmpty( ) --> Remove all items
// void decreaseKey( PairNode p, newVal )
// --> Decrease value in node p
// ******************ERRORS********************************
// Throws Underflow as warranted
// Node and forward declaration because g++ does
// not understand nested classes.
{
T element;
element( theElement ),
{ }
};
{
};
/**
* Pairing heap datastructure implementation.
*
* Based on example code in "Data structures and Algorithm Analysis in C++"
* by Mark Allen Weiss, used and released under the LGPL by permission
* of the author.
*/
{
virtual ~PairingHeap( );
bool isEmpty( ) const;
bool isFull( ) const;
int size();
const T & findMin( ) const;
void deleteMin( );
const T extractMin( ) {
T v = findMin();
deleteMin();
return v;
}
void makeEmpty( );
{
}
} else {
}
}
return r;
}
int counter;
void reclaimMemory( PairNode<T> *t ) const;
};
#include "PairingHeap.cpp"
#endif