Template Class Meap

Defined in File Meap.hpp

Class Documentation

template<typename KeyT, typename ValueT> class Meap

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().

Public Functions

inline Meap(): Initializes an empty meap.

Meap(size_t capacity): Initializes an empty meap and reserves memory for at least capacity many elements.

bool containsKey(KeyT key) const

boost::optional<ValueT> insert(KeyT key, const ValueT &value)

boost::optional<ValueT> erase(KeyT key)

void clear()

boost::optional<const ValueT&> get(KeyT key) const

size_t numValues() const

const MeapPair<KeyT, ValueT> &peekMin() const: Returns a reference to the minimal value with its corresponding key.

MeapPair<KeyT, ValueT> popMin(): Removes the minimal value with its corresponding key from the meap and returns it.

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

bool isEmpty() const: Returns true iff the meap is empty.