Template Class PrioQueue

Class Documentation

template<class Key, class Value>
class PrioQueue

Priority queue with extract-min and decrease-key. The type Val takes on integer values between 0 and n-1. O(n log n) for construction, O(log n) for typical operations.

Public Functions

PrioQueue(const std::vector<Key> &keys)

Builds priority queue from the vector keys, values are indices of keys.

PrioQueue(uint64_t capacity)

Builds priority queue of the specified capacity capacity.

virtual ~PrioQueue() = default

Default destructor

virtual void insert(Key key, Value value)

Inserts key-value pair stored in elem.

virtual ElemType peekMin(size_t n = 0)

Returns the n-th element in the priority queue.

virtual ElemType extractMin()

Removes the element with minimum key and returns it.

virtual void changeKey(Key newKey, Value value)

Modifies entry with value value. The entry is then set to newKey with the same value. If the corresponding key is not present, the element will be inserted.

virtual uint64_t size() const
Returns:

Number of elements in PQ.

virtual bool empty() const noexcept
Returns:

Whether or not the PQ is empty.

virtual bool contains(const Value &value) const
Returns:

Whether or not the PQ contains the given value.

virtual void remove(const Value &val)

Removes key-value pair given by value val.

virtual void clear()

Removes all the elements from the priority queue.

template<typename L>
void forElements(L handle) const

Iterates over all the elements of the priority queue and call handle (lambda closure).

template<typename C, typename L>
void forElementsWhile(C condition, L handle) const

Iterates over all the elements of the priority queue while the condition is satisfied and call handle (lambda closure).

inline virtual void print()

DEBUGGING

Protected Functions

PrioQueue() = default

Default constructor without functionality. Only here for derived classes!

virtual void remove(const ElemType &elem)

Removes key-value pair given by elem.

virtual std::set<std::pair<Key, Value>> content() const
Returns:

current content of queue