PairingHeap< T > Class Template Reference

Pairing heap datastructure implementation. More...

#include <PairingHeap.h>

Public Member Functions
	PairingHeap (bool(*lessThan)(T const &lhs, T const &rhs))
	~PairingHeap ()
bool	isEmpty () const
PairNode< T > *	insert (const T &x)
const T &	findMin () const
void	deleteMin ()
void	makeEmpty ()
void	merge (PairingHeap< T > *rhs)
	PairingHeap (const PairingHeap &rhs)=delete
	PairingHeap (PairingHeap &&rhs)=delete
PairingHeap &	operator= (const PairingHeap &rhs)=delete
PairingHeap &	operator= (PairingHeap &&rhs)=delete

Protected Member Functions
PairNode< T > *	getRoot ()

Friends
std::ostream &	operator<< (std::ostream &os, const PairingHeap< T > &b)

Detailed Description

template<class T>
class PairingHeap< T >

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 tgdwy.nosp@m.er@g.nosp@m.mail..nosp@m.com

Copyright (C) 2005 Authors

This version is released under the CPL (Common Public License) with the Graphviz distribution. A version is also available under the LGPL as part of the Adaptagrams project: https://github.com/mjwybrow/adaptagrams.
If you make improvements or bug fixes to this code it would be much appreciated if you could also contribute those changes back to the Adaptagrams repository.

Definition at line 67 of file PairingHeap.h.

Constructor & Destructor Documentation

PairingHeap() [1/3]

template<class T >

PairingHeap< T >::PairingHeap

(

bool(*)(T const &lhs, T const &rhs)

lessThan

)

Construct the pairing heap.

Definition at line 37 of file PairingHeap.cpp.

~PairingHeap()

template<class T >

PairingHeap< T >::~PairingHeap

(

)

Destroy the leftist heap.

Definition at line 48 of file PairingHeap.cpp.

PairingHeap() [2/3]

template<class T >

PairingHeap< T >::PairingHeap ( const PairingHeap< T > &  rhs )

delete

PairingHeap() [3/3]

template<class T >

PairingHeap< T >::PairingHeap ( PairingHeap< T > &&  rhs )

delete

Member Function Documentation

deleteMin()

template<class T >

void PairingHeap< T >::deleteMin

(

)

Remove the smallest item from the priority queue. Throws Underflow if empty.

Definition at line 85 of file PairingHeap.cpp.

findMin()

template<class T >

const T & PairingHeap< T >::findMin

(

)

const

Find the smallest item in the priority queue. Return the smallest item, or throw Underflow if empty.

Definition at line 74 of file PairingHeap.cpp.

getRoot()

template<class T >

PairNode< T > * PairingHeap< T >::getRoot ( )

inlineprotected

Definition at line 97 of file PairingHeap.h.

Referenced by PairingHeap< T >::merge().

Here is the caller graph for this function:

insert()

template<class T >

PairNode< T > * PairingHeap< T >::insert

(

const T &

x

)

Insert item x into the priority queue, maintaining heap order. Return a pointer to the node containing the new item.

Definition at line 59 of file PairingHeap.cpp.

References newNode().

Here is the call graph for this function:

isEmpty()

template<class T >

bool PairingHeap< T >::isEmpty

(

)

const

Test if the priority queue is logically empty. Returns true if empty, false otherwise.

Definition at line 104 of file PairingHeap.cpp.

makeEmpty()

template<class T >

void PairingHeap< T >::makeEmpty

(

)

Make the priority queue logically empty.

Definition at line 113 of file PairingHeap.cpp.

merge()

template<class T >

void PairingHeap< T >::merge ( PairingHeap< T > *  rhs )

inline

Definition at line 80 of file PairingHeap.h.

References PairingHeap< T >::getRoot().

Here is the call graph for this function:

operator=() [1/2]

template<class T >

PairingHeap & PairingHeap< T >::operator= ( const PairingHeap< T > &  rhs )

delete

operator=() [2/2]

template<class T >

PairingHeap & PairingHeap< T >::operator= ( PairingHeap< T > &&  rhs )

delete

Friends And Related Symbol Documentation

operator<<

template<class T >

std::ostream & operator<< ( std::ostream &  os, const PairingHeap< T > &  b  )

friend

---

The documentation for this class was generated from the following files:

• lib/vpsc/pairingheap/PairingHeap.h
• lib/vpsc/pairingheap/PairingHeap.cpp