Fibonacci heap. More...
#include <FibonacciHeap.h>
Inheritance diagram for PLCore::FibonacciHeap< KeyType, ValueType, Comparer >:
Public Member Functions | |
| FibonacciHeap () | |
| Constructor. | |
| virtual | ~FibonacciHeap () |
| Destructor. | |
| bool | IsNormalized () |
| Returns whether the Fibonacci heap is normalized or not. | |
| bool | Consolidate () |
| Consolidate. | |
| virtual Iterator< ValueType > | GetIterator (uint32 nIndex=0) const override |
| Returns an iterator operating on the derived data structure. | |
| virtual ConstIterator< ValueType > | GetConstIterator (uint32 nIndex=0) const override |
| Returns a constant iterator operating on the derived data structure. | |
| virtual Iterator< ValueType > | GetEndIterator () const override |
| Returns an iterator operating on the derived data structure and starting at the end. | |
| virtual ConstIterator< ValueType > | GetConstEndIterator () const override |
| Returns a constant iterator operating on the derived data structure and starting at the end. | |
| virtual void | Clear () override |
| Clears the heap. | |
| virtual bool | IsEmpty () const override |
| Checks whether the heap is complete empty. | |
| virtual uint32 | GetNumOfElements () const override |
| Returns the number of elements. | |
| virtual bool | Add (const KeyType &Key, const ValueType &Value) override |
| Adds a new element to the heap. | |
| virtual bool | GetTop (ValueType *pValue=nullptr, KeyType *pKey=nullptr) const override |
| Returns the value of the top element. | |
| virtual bool | ExtractTop (ValueType *pValue=nullptr, KeyType *pKey=nullptr) override |
| Returns the value of the top element and removes it from the heap. | |
Detailed Description
template<class KeyType, class ValueType, class Comparer = CompareFunction>
class PLCore::FibonacciHeap< KeyType, ValueType, Comparer >
Fibonacci heap.
Constructor & Destructor Documentation
template<class KeyType , class ValueType , class Comparer >
| PLCore::FibonacciHeap< KeyType, ValueType, Comparer >::FibonacciHeap | ( | ) |
template<class KeyType , class ValueType , class Comparer >
| PLCore::FibonacciHeap< KeyType, ValueType, Comparer >::~FibonacciHeap | ( | ) | [virtual] |
Destructor.
Member Function Documentation
template<class KeyType , class ValueType , class Comparer >
| bool PLCore::FibonacciHeap< KeyType, ValueType, Comparer >::IsNormalized | ( | ) |
Returns whether the Fibonacci heap is normalized or not.
- Returns:
- 'true' if the Fibonacci heap is normalized, else 'false'
- Remarks:
- A Fibonacci heap is normalized if there are no tree's within the tree list with the same degree. After 'ExtractTop()' the heap is always normalized.
template<class KeyType , class ValueType , class Comparer >
| bool PLCore::FibonacciHeap< KeyType, ValueType, Comparer >::Consolidate | ( | ) |
Consolidate.
- Remarks:
- 'Cleanup' function. This function is called during the extraction of the top element automatically. After the execution of this function the heap is 'normalized'.
- Returns:
- 'true' if all went fine, else 'false' (maybe consolidate is not required)
template<class KeyType , class ValueType , class Comparer >
| Iterator< ValueType > PLCore::FibonacciHeap< KeyType, ValueType, Comparer >::GetIterator | ( | uint32 | nIndex = 0 | ) | const [override, virtual] |
Returns an iterator operating on the derived data structure.
- Parameters:
-
[in] nIndex Start index, if >= 'total number of elements' the index is set to the last valid index
- Returns:
- Iterator operating on the derived
Implements PLCore::Iterable< ValueType >.
template<class KeyType , class ValueType , class Comparer >
| ConstIterator< ValueType > PLCore::FibonacciHeap< KeyType, ValueType, Comparer >::GetConstIterator | ( | uint32 | nIndex = 0 | ) | const [override, virtual] |
Returns a constant iterator operating on the derived data structure.
- Parameters:
-
[in] nIndex Start index, if >= 'total number of elements' the index is set to the last valid index
- Returns:
- Constant iterator operating on the derived
Implements PLCore::Iterable< ValueType >.
template<class KeyType , class ValueType , class Comparer >
| Iterator< ValueType > PLCore::FibonacciHeap< KeyType, ValueType, Comparer >::GetEndIterator | ( | ) | const [override, virtual] |
Returns an iterator operating on the derived data structure and starting at the end.
- Returns:
- Iterator operating on the derived,
- Remarks:
- Use this function to get an iterator if you want to iterate in reversed order starting at the end last element.
Implements PLCore::Iterable< ValueType >.
template<class KeyType , class ValueType , class Comparer >
| ConstIterator< ValueType > PLCore::FibonacciHeap< KeyType, ValueType, Comparer >::GetConstEndIterator | ( | ) | const [override, virtual] |
Returns a constant iterator operating on the derived data structure and starting at the end.
- Returns:
- Constant iterator operating on the derived,
- Remarks:
- Use this function to get a constant iterator if you want to iterate in reversed order starting at the end last element.
Implements PLCore::Iterable< ValueType >.
template<class KeyType , class ValueType , class Comparer >
| void PLCore::FibonacciHeap< KeyType, ValueType, Comparer >::Clear | ( | ) | [override, virtual] |
Clears the heap.
Implements PLCore::Heap< KeyType, ValueType >.
template<class KeyType , class ValueType , class Comparer >
| bool PLCore::FibonacciHeap< KeyType, ValueType, Comparer >::IsEmpty | ( | ) | const [override, virtual] |
Checks whether the heap is complete empty.
- Returns:
- 'true' if the heap is empty, else 'false'
Implements PLCore::Heap< KeyType, ValueType >.
template<class KeyType , class ValueType , class Comparer >
| uint32 PLCore::FibonacciHeap< KeyType, ValueType, Comparer >::GetNumOfElements | ( | ) | const [override, virtual] |
Returns the number of elements.
- Returns:
- Number of container elements
Implements PLCore::Heap< KeyType, ValueType >.
template<class KeyType , class ValueType , class Comparer >
| bool PLCore::FibonacciHeap< KeyType, ValueType, Comparer >::Add | ( | const KeyType & | Key, |
| const ValueType & | Value | ||
| ) | [override, virtual] |
Adds a new element to the heap.
- Parameters:
-
[in] Key The key of the new element [in] Value The value of the new element
- Returns:
- 'true' if all went fine, else 'false'
- Note:
- You have to check by yourself whether there's already such a key within the heap
Implements PLCore::Heap< KeyType, ValueType >.
template<class KeyType , class ValueType , class Comparer >
| bool PLCore::FibonacciHeap< KeyType, ValueType, Comparer >::GetTop | ( | ValueType * | pValue = nullptr, |
| KeyType * | pKey = nullptr |
||
| ) | const [override, virtual] |
Returns the value of the top element.
- Parameters:
-
[out] pValue If not a null pointer, this will receive the value of the top element [out] pKey If not a null pointer, this will receive the key of the top element
- Returns:
- 'true' if all went fine, else 'false'
Implements PLCore::Heap< KeyType, ValueType >.
template<class KeyType , class ValueType , class Comparer >
| bool PLCore::FibonacciHeap< KeyType, ValueType, Comparer >::ExtractTop | ( | ValueType * | pValue = nullptr, |
| KeyType * | pKey = nullptr |
||
| ) | [override, virtual] |
Returns the value of the top element and removes it from the heap.
- Parameters:
-
[out] pValue If not a null pointer, this will receive the value of the top element [out] pKey If not a null pointer, this will receive the key of the top element
- Returns:
- 'true' if all went fine, else 'false'
Implements PLCore::Heap< KeyType, ValueType >.
The documentation for this class was generated from the following files:
