Template Class BucketPriorityQueue¶

Inheritance Relationships¶

Class Documentation¶

template<SignedIntegral KeyType = int64_t, IntegralValue ValueType = index>
class BucketPriorityQueue : public Aux::PrioQueue<int64_t, index>¶

Addressable priority queue for values in the range [0,n) and integer keys (= priorities) in the range [minPrio, maxPrio]. minPrio and maxPrio can be positive or negative, respectively with the obvious constraint minPrio <= maxPrio. Amortized constant running time for each operation.

Public Functions

BucketPriorityQueue(std::span<const KeyType> keys, KeyType minAdmissibleKey, KeyType maxAdmissibleKey)¶

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

Parameters:

• keys – [in] Vector of keys

• minAdmissibleKey – [in] Minimum admissible key

• maxAdmissibleKey – [in] Maximum admissible key

BucketPriorityQueue(uint64_t capacity, KeyType minAdmissibleKey, KeyType maxAdmissibleKey)¶

Builds priority queue of the specified capacity capacity.

~BucketPriorityQueue() override = default¶

Default destructor

void insert(KeyType key, ValueType value) override¶

Inserts key-value pair (@key, @value).

std::pair<KeyType, ValueType> getMin()¶

Returns the element on top of the PrioQ.

virtual std::pair<KeyType, ValueType> extractMin() override¶

Removes the element with minimum key and returns the key-value pair.

void changeKey(KeyType newKey, ValueType value) override¶

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 override¶

Returns:

Number of elements in PQ.

virtual bool empty() const noexcept override¶

Returns:

Whether or not the PQ is empty.

bool contains(const ValueType &value) const override¶

Returns:

Whether or not the PQ contains the given element.

void remove(const ValueType &value) override¶

Removes key-value pair given by value val.

virtual void clear() override¶

Removes all elements from the priority queue.

virtual KeyType getKey(const ValueType &val)¶

Returns:

key to given value @val.