Open
Graph Drawing
Framework

 v. 2022.02 (Dogwood)
 

ogdf::PairingHeap< T, C > Class Template Reference

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. More...
 
virtual ~PairingHeap ()
 Destructs pairing heap. More...
 
void decrease (PairingHeapNode< T > *heapNode, const T &value) override
 Decreases value of the given heapNode to value. More...
 
void merge (PairingHeap< T, C > &other) override
 Merges in values of other heap. More...
 
void pop () override
 Removes the top element from the heap. More...
 
PairingHeapNode< T > * push (const T &value) override
 Inserts a new node with given value into a heap. More...
 
const T & top () const override
 Returns reference to the top element in the heap. More...
 
const T & value (PairingHeapNode< T > *heapNode) const override
 Returns the value of the node. More...
 
- Public Member Functions inherited from ogdf::HeapBase< PairingHeap< T, C >, PairingHeapNode< T >, T, C >
 HeapBase (C const &comp=C())
 
virtual const C & comparator () const
 Returns the comparator used to sort the values in the heap. More...
 
virtual void decrease (Handle handle, const T &value)=0
 Decreases a single value. More...
 
virtual const T & top () const=0
 Returns the topmost value in the heap. More...
 
virtual const T & value (const Handle handle) const=0
 Returns the value of that handle. More...
 

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. More...
 
PairingHeapNode< T > * pair (PairingHeapNode< T > *heapNode)
 Pairs list of heaps given as heapNode. Returns resulting list. More...
 

Static Private Member Functions

static void link (PairingHeapNode< T > *parent, PairingHeapNode< T > *child)
 Makes child node a child of parent node. More...
 
static void release (PairingHeapNode< T > *heapNode)
 Releases memory occupied by list of heaps given as heapNode. More...
 
static void unlink (PairingHeapNode< T > *heapNode)
 Removes heapNode from its parent children list. More...
 

Private Attributes

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

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. More...
 

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
TDenotes value type of inserted elements.
CDenotes comparison functor determining value ordering.

Definition at line 72 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 74 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
cmpComparison functor determining value ordering.
initialSizeignored by this implementation.

Definition at line 160 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 165 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
heapNodeA node for which the value is to be decreased.
valueA new value for the node.

Definition at line 201 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 280 of file PairingHeap.h.

◆ merge() [1/2]

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

Merges in values of other heap.

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

Parameters
otherA heap to be merged in.

Reimplemented from ogdf::HeapBase< PairingHeap< T, C >, PairingHeapNode< T >, T, C >.

Definition at line 212 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 266 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 220 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 191 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
valueA value to be inserted.
Returns
Handle to the inserted node.

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

Definition at line 181 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 310 of file PairingHeap.h.

◆ top()

template<typename T , typename C >
const T & ogdf::PairingHeap< T, C >::top
inlineoverride

Returns reference to the top element in the heap.

Definition at line 173 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 293 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
heapNodeThe nodes handle
Returns
the value of the node

Definition at line 137 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 142 of file PairingHeap.h.


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