1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
|
/**
* \brief 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.
*
* 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.
template <class T>
class PairingHeap;
template <class T>
std::ostream& operator<< (std::ostream &os,const PairingHeap<T> &b);
template <class T>
class PairNode
{
friend std::ostream& operator<< <T>(std::ostream &os,const PairingHeap<T> &b);
T element;
PairNode *leftChild;
PairNode *nextSibling;
PairNode *prev;
PairNode( const T & theElement ) :
element( theElement ),
leftChild(NULL), nextSibling(NULL), prev(NULL)
{ }
friend class PairingHeap<T>;
};
template <class T>
class Comparator
{
public:
virtual bool isLessThan(T const &lhs, T const &rhs) const = 0;
};
template <class T>
class PairingHeap
{
friend std::ostream& operator<< <T>(std::ostream &os,const PairingHeap<T> &b);
public:
PairingHeap( bool (*lessThan)(T const &lhs, T const &rhs) );
PairingHeap( const PairingHeap & rhs );
virtual ~PairingHeap( );
bool isEmpty( ) const;
bool isFull( ) const;
int size();
PairNode<T> *insert( const T & x );
const T & findMin( ) const;
void deleteMin( );
const T extractMin( ) {
T v = findMin();
deleteMin();
return v;
}
void makeEmpty( );
void decreaseKey( PairNode<T> *p, const T & newVal );
void merge( PairingHeap<T> *rhs )
{
PairNode<T> *broot=rhs->getRoot();
if (root == NULL) {
if(broot != NULL) {
root = broot;
}
} else {
compareAndLink(root, broot);
}
counter+=rhs->size();
}
const PairingHeap & operator=( const PairingHeap & rhs );
protected:
PairNode<T> * getRoot() {
PairNode<T> *r=root;
root=NULL;
return r;
}
private:
PairNode<T> *root;
bool (*lessThan)(T const &lhs, T const &rhs);
int counter;
void reclaimMemory( PairNode<T> *t ) const;
void compareAndLink( PairNode<T> * & first, PairNode<T> *second ) const;
PairNode<T> * combineSiblings( PairNode<T> *firstSibling ) const;
PairNode<T> * clone( PairNode<T> * t ) const;
};
#include "PairingHeap.cpp"
#endif
|
