Binomial heap implementation. More...
#include <ogdf/basic/heap/BinomialHeap.h>
Public Member Functions | |
BinomialHeap (const C &cmp=C(), int initialSize=-1) | |
Creates empty binomial heap. More... | |
virtual | ~BinomialHeap () |
Destructs the heap. More... | |
void | decrease (BinomialHeapNode< T > *heapNode, const T &value) override |
Decreases value of the given heapNode to value . More... | |
void | merge (BinomialHeap< T, C > &other) override |
Merges in values of other heap. More... | |
void | pop () override |
Removes the top element from the heap. More... | |
BinomialHeapNode< 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 (BinomialHeapNode< T > *heapNode) const override |
Returns the value of the node. More... | |
Public Member Functions inherited from ogdf::HeapBase< BinomialHeap< T, std::less< T > >, BinomialHeapNode< T >, T, std::less< T > > | |
HeapBase (const std::less< T > &comp=std::less< T >()) | |
virtual const std::less< T > & | 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 void | merge (BinomialHeap< T, std::less< T > > &other) |
Merges in values of other heap. 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< BinomialHeap< T, C >, BinomialHeapNode< T >, T, C > |
Private Member Functions | |
BinomialHeapNode< T > * | join (BinomialHeapNode< T > *a, BinomialHeapNode< T > *b) |
Joins heap lists a and b into single list sorted by the ranks. More... | |
void | merge (BinomialHeapNode< T > *other) |
Merges in other heap list into the heap. More... | |
Static Private Member Functions | |
static void | link (BinomialHeapNode< T > *parent, BinomialHeapNode< T > *child) |
Makes child node a child of parent node. More... | |
static void | release (BinomialHeapNode< T > *heapNode) |
Releases memory occupied by list of heaps given as heapNode . More... | |
Private Attributes | |
BinomialHeapNode< T > * | m_root |
Root node of the heap. More... | |
Additional Inherited Members | |
Public Types inherited from ogdf::HeapBase< BinomialHeap< T, std::less< T > >, BinomialHeapNode< T >, T, std::less< T > > | |
using | Handle = BinomialHeapNode< T > * |
The type of handle used to identify stored values. More... | |
Binomial heap implementation.
Code is mainly based on samples and ideas provided in "Introduction to Algorithms" book (aka "Cormen").
T | Denotes value type of inserted elements. |
C | Denotes comparison functor determining value ordering. |
Definition at line 73 of file BinomialHeap.h.
|
private |
Definition at line 74 of file BinomialHeap.h.
|
explicit |
Creates empty binomial heap.
cmp | Comparison functor determining value ordering. |
initialSize | ignored by this implementation. |
Definition at line 155 of file BinomialHeap.h.
|
virtual |
Destructs the heap.
If the heap is not empty, destructors of contained elements are called and used storage is deallocated.
Definition at line 159 of file BinomialHeap.h.
|
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.
heapNode | A node for which the value is to be decreased. |
value | A new value for the node. |
Definition at line 226 of file BinomialHeap.h.
|
inlineprivate |
Joins heap lists a
and b
into single list sorted by the ranks.
Definition at line 246 of file BinomialHeap.h.
|
inlinestaticprivate |
Makes child
node a child of parent
node.
Definition at line 313 of file BinomialHeap.h.
|
override |
Merges in values of other
heap.
After merge other
heap becomes empty and is valid for further usage.
other | A heap to be merged in. |
Definition at line 240 of file BinomialHeap.h.
|
inlineprivate |
Merges in other
heap list into the heap.
Definition at line 281 of file BinomialHeap.h.
|
overridevirtual |
Removes the top element from the heap.
Behaviour of this function is undefined if the heap is empty.
Implements ogdf::HeapBase< BinomialHeap< T, std::less< T > >, BinomialHeapNode< T >, T, std::less< T > >.
Definition at line 196 of file BinomialHeap.h.
|
overridevirtual |
Inserts a new node with given value
into a heap.
value | A value to be inserted. |
Implements ogdf::HeapBase< BinomialHeap< T, std::less< T > >, BinomialHeapNode< T >, T, std::less< T > >.
Definition at line 188 of file BinomialHeap.h.
|
staticprivate |
Releases memory occupied by list of heaps given as heapNode
.
Definition at line 165 of file BinomialHeap.h.
|
inlineoverride |
Returns reference to the top element in the heap.
Definition at line 176 of file BinomialHeap.h.
|
inlineoverride |
Returns the value of the node.
heapNode | The nodes handle |
Definition at line 137 of file BinomialHeap.h.
|
private |
Root node of the heap.
Definition at line 140 of file BinomialHeap.h.