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