A map combined with a binary heap. More...
#include <Meap.hpp>
Public Member Functions | |
| void | clear () |
| bool | containsKey (KeyT key) const |
| boost::optional< ValueT > | erase (KeyT key) |
| boost::optional< const ValueT & > | get (KeyT key) const |
| boost::optional< ValueT > | insert (KeyT key, const ValueT &value) |
| bool | isEmpty () const |
Returns true iff the meap is empty. More... | |
| Meap () | |
| Initializes an empty meap. More... | |
| Meap (size_t capacity) | |
Initializes an empty meap and reserves memory for at least capacity many elements. More... | |
| size_t | numValues () const |
| const MeapPair< KeyT, ValueT > & | peekMin () const |
| Returns a reference to the minimal value with its corresponding key. More... | |
| MeapPair< KeyT, ValueT > | popMin () |
| Removes the minimal value with its corresponding key from the meap and returns it. More... | |
| void | updateValue (const KeyT &key, const ValueT &newValue) |
Updates the value of key to newValue and repairs the heap. More... | |
Private Member Functions | |
| void | bubbleDown (size_t idx) |
Performs the bubbleDown() heap operation on the node at idx. More... | |
| void | bubbleUp (size_t idx) |
Performs the bubbleUp heap operation on the node at idx. More... | |
| void | debugOutput () const |
| Just for debugging purposes. Prints a bunch of information. More... | |
| size_t | father (size_t child) const |
Returns the index of the father of the child at index child. More... | |
| size_t | leftChild (size_t father) const |
Returns the index of the left child of the father at index father. More... | |
| size_t | rightChild (size_t father) const |
Returns the index of the right child of the father at index father. More... | |
Private Attributes | |
| std::vector< MeapPair< KeyT, ValueT > > | m_heap |
| unordered_map< KeyT, size_t > | m_indices |
A map combined with a binary heap.
The elements in the meap are pairs of KeyT and ValueT. Only the latter is used for sorting the heap. The former can be used to lookup the value, as in a regular map. Combining both, a map and a heap, allows to implement the updateValue() method, which would otherwise be impossible with a simple binary heap. In this library, this type is often used with some kind of "cost" as value and a handle as key.
This implementation is a min heap: the smallest value sits "at the top" and can be retrieved in O(1) via popMin() or peekMin().
|
inline |
| lvr2::Meap< KeyT, ValueT >::Meap | ( | size_t | capacity | ) |
Initializes an empty meap and reserves memory for at least capacity many elements.
|
private |
Performs the bubbleDown() heap operation on the node at idx.
|
private |
Performs the bubbleUp heap operation on the node at idx.
As long as the father of the node at idx still has a greater value than the value of idx, both are swapped.
| void lvr2::Meap< KeyT, ValueT >::clear | ( | ) |
| bool lvr2::Meap< KeyT, ValueT >::containsKey | ( | KeyT | key | ) | const |
|
private |
Just for debugging purposes. Prints a bunch of information.
| boost::optional<ValueT> lvr2::Meap< KeyT, ValueT >::erase | ( | KeyT | key | ) |
|
private |
Returns the index of the father of the child at index child.
| boost::optional<const ValueT&> lvr2::Meap< KeyT, ValueT >::get | ( | KeyT | key | ) | const |
| boost::optional<ValueT> lvr2::Meap< KeyT, ValueT >::insert | ( | KeyT | key, |
| const ValueT & | value | ||
| ) |
| bool lvr2::Meap< KeyT, ValueT >::isEmpty | ( | ) | const |
Returns true iff the meap is empty.
|
private |
Returns the index of the left child of the father at index father.
| size_t lvr2::Meap< KeyT, ValueT >::numValues | ( | ) | const |
| const MeapPair<KeyT, ValueT>& lvr2::Meap< KeyT, ValueT >::peekMin | ( | ) | const |
Returns a reference to the minimal value with its corresponding key.
| MeapPair<KeyT, ValueT> lvr2::Meap< KeyT, ValueT >::popMin | ( | ) |
Removes the minimal value with its corresponding key from the meap and returns it.
|
private |
Returns the index of the right child of the father at index father.
| void lvr2::Meap< KeyT, ValueT >::updateValue | ( | const KeyT & | key, |
| const ValueT & | newValue | ||
| ) |
Updates the value of key to newValue and repairs the heap.
The new value might be lower or greater than the old value. The heap is repaired either way. If the new value equals the old one, this method does nothing.
|
private |
|
private |