Pairing heap implementation. More...

#include <ogdf/basic/heap/PairingHeap.h>

Inheritance diagram for ogdf::PairingHeap< T, C >:

Public Member Functions
	PairingHeap (const C &cmp=C(), int initialSize=-1)
	Creates empty pairing heap.

virtual	~PairingHeap ()
	Destructs pairing heap.

void	decrease (PairingHeapNode< T > *heapNode, const T &value) override
	Decreases value of the given `heapNode` to `value`.

void	merge (PairingHeap< T, C > &other) override
	Merges in values of `other` heap.

void	pop () override
	Removes the top element from the heap.

PairingHeapNode< T > *	push (const T &value) override
	Inserts a new node with given `value` into a heap.

const T &	top () const override
	Returns reference to the top element in the heap.

const T &	value (PairingHeapNode< T > *heapNode) const override
	Returns the value of the node.

Public Member Functions inherited from ogdf::HeapBase< PairingHeap< T, C >, PairingHeapNode< T >, T, C >
	HeapBase (const C &comp=C())

virtual const C &	comparator () const
	Returns the comparator used to sort the values in the heap.

virtual void	decrease (Handle handle, const T &value)=0
	Decreases a single value.

virtual void	merge (PairingHeap< T, C > &other)
	Merges in values of `other` heap.

virtual const T &	value (const Handle handle) const=0
	Returns the value of that handle.

Private Types
using	base_type = HeapBase< PairingHeap< T, C >, PairingHeapNode< T >, T, C >

Private Member Functions
PairingHeapNode< T > *	merge (PairingHeapNode< T > a, PairingHeapNode< T > b)
	Merges lists of heaps `a` and `b`. Returns resulting list.

PairingHeapNode< T > *	pair (PairingHeapNode< T > *heapNode)
	Pairs list of heaps given as `heapNode`. Returns resulting list.

Static Private Member Functions
static void	link (PairingHeapNode< T > parent, PairingHeapNode< T > child)
	Makes `child` node a child of `parent` node.

static void	release (PairingHeapNode< T > *heapNode)
	Releases memory occupied by list of heaps given as `heapNode`.

static void	unlink (PairingHeapNode< T > *heapNode)
	Removes `heapNode` from its parent children list.

Private Attributes
PairingHeapNode< T > *	m_root
	Root node of the heap.

Additional Inherited Members
Public Types inherited from ogdf::HeapBase< PairingHeap< T, C >, PairingHeapNode< T >, T, C >
using	Handle = PairingHeapNode< T > *
	The type of handle used to identify stored values.

Detailed Description

template<typename T, typename C>
class ogdf::PairingHeap< T, C >

Pairing heap implementation.

Code is mainly based on orginal paper "The Pairing Heap: A New Form of Self-Adjusting Heap" by Fredman, Sedgewick, Sleator and Tarjan.

Template Parameters

T	Denotes value type of inserted elements.
C	Denotes comparison functor determining value ordering.

Definition at line 70 of file PairingHeap.h.

Member Typedef Documentation

◆ base_type

template<typename T , typename C >

using ogdf::PairingHeap< T, C >::base_type = HeapBase<PairingHeap<T, C>, PairingHeapNode<T>, T, C>

private

Definition at line 71 of file PairingHeap.h.

Constructor & Destructor Documentation

◆ PairingHeap()

template<typename T , typename C >

ogdf::PairingHeap< T, C >::PairingHeap	(	const C &	cmp = `C()`,
		int	initialSize = `-1`
	)

explicit

Creates empty pairing heap.

Parameters

cmp	Comparison functor determining value ordering.
initialSize	ignored by this implementation.

Definition at line 154 of file PairingHeap.h.

◆ ~PairingHeap()

template<typename T , typename C >

ogdf::PairingHeap< T, C >::~PairingHeap ( )

virtual

Destructs pairing heap.

If the heap is not empty, destructors of contained elements are called and used storage is deallocated.

Definition at line 158 of file PairingHeap.h.

Member Function Documentation

◆ decrease()

template<typename T , typename C >

void ogdf::PairingHeap< T, C >::decrease	(	PairingHeapNode< T > *	heapNode,
		const T &	value
	)

override

Decreases value of the given heapNode to value.

Behaviour of this function is undefined if node does not belong to a the heap or new value is greater than old one.

Parameters

heapNode	A node for which the value is to be decreased.
value	A new value for the node.

Definition at line 186 of file PairingHeap.h.

◆ link()

template<typename T , typename C >

void ogdf::PairingHeap< T, C >::link	(	PairingHeapNode< T > *	parent,
		PairingHeapNode< T > *	child
	)

inlinestaticprivate

Makes child node a child of parent node.

Definition at line 255 of file PairingHeap.h.

◆ merge() [1/2]

template<typename T , typename C >

void ogdf::PairingHeap< T, C >::merge ( PairingHeap< T, C > & other )

override

Merges in values of other heap.

After merge other heap becomes empty and is valid for further usage.

Parameters

other A heap to be merged in.

Definition at line 195 of file PairingHeap.h.

◆ merge() [2/2]

template<typename T , typename C >

PairingHeapNode< T > * ogdf::PairingHeap< T, C >::merge	(	PairingHeapNode< T > *	a,
		PairingHeapNode< T > *	b
	)

inlineprivate

Merges lists of heaps a and b. Returns resulting list.

Definition at line 244 of file PairingHeap.h.

◆ pair()

template<typename T , typename C >

PairingHeapNode< T > * ogdf::PairingHeap< T, C >::pair ( PairingHeapNode< T > * heapNode )

inlineprivate

Pairs list of heaps given as heapNode. Returns resulting list.

Definition at line 201 of file PairingHeap.h.

◆ pop()

template<typename T , typename C >

void ogdf::PairingHeap< T, C >::pop ( )

overridevirtual

Removes the top element from the heap.

Behaviour of this function is undefined if the heap is empty.

Implements ogdf::HeapBase< PairingHeap< T, C >, PairingHeapNode< T >, T, C >.

Definition at line 178 of file PairingHeap.h.

◆ push()

template<typename T , typename C >

PairingHeapNode< T > * ogdf::PairingHeap< T, C >::push ( const T & value )

overridevirtual

Inserts a new node with given value into a heap.

Parameters

value A value to be inserted.

Returns: Handle to the inserted node.

Implements ogdf::HeapBase< PairingHeap< T, C >, PairingHeapNode< T >, T, C >.

Definition at line 170 of file PairingHeap.h.

◆ release()

template<typename T , typename C >

void ogdf::PairingHeap< T, C >::release ( PairingHeapNode< T > * heapNode )

inlinestaticprivate

Releases memory occupied by list of heaps given as heapNode.

Definition at line 279 of file PairingHeap.h.

◆ top()

template<typename T , typename C >

const T & ogdf::PairingHeap< T, C >::top ( ) const

inlineoverridevirtual

Returns reference to the top element in the heap.

Implements ogdf::HeapBase< PairingHeap< T, C >, PairingHeapNode< T >, T, C >.

Definition at line 164 of file PairingHeap.h.

◆ unlink()

template<typename T , typename C >

void ogdf::PairingHeap< T, C >::unlink ( PairingHeapNode< T > * heapNode )

inlinestaticprivate

Removes heapNode from its parent children list.

Definition at line 265 of file PairingHeap.h.

◆ value()

template<typename T , typename C >

const T & ogdf::PairingHeap< T, C >::value ( PairingHeapNode< T > * heapNode ) const

inlineoverride

Returns the value of the node.

Parameters

heapNode The nodes handle

Returns: the value of the node

Definition at line 134 of file PairingHeap.h.

Member Data Documentation

◆ m_root

template<typename T , typename C >

PairingHeapNode<T>* ogdf::PairingHeap< T, C >::m_root

private

Root node of the heap.

Definition at line 137 of file PairingHeap.h.

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

include/ogdf/basic/heap/PairingHeap.h

OpenGraph DrawingFramework

Public Member Functions

Private Types

Private Member Functions

Static Private Member Functions

Private Attributes

Additional Inherited Members

Detailed Description

Member Typedef Documentation

◆ base_type

Constructor & Destructor Documentation

◆ PairingHeap()

◆ ~PairingHeap()

Member Function Documentation

◆ decrease()

◆ link()

◆ merge() [1/2]

◆ merge() [2/2]

◆ pair()

◆ pop()

◆ push()

◆ release()

◆ top()

◆ unlink()

◆ value()

Member Data Documentation

◆ m_root

Open
Graph Drawing
Framework