Class BucketPQ

Nested Relationships

Nested Types

Inheritance Relationships

Base Type

Class Documentation

class BucketPQ : 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

BucketPQ(const std::vector<int64_t> &keys, int64_t minAdmissibleKey, int64_t maxAdmissibleKey)

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

  • keys[in] Vector of keys

  • minAdmissibleKey[in] Minimum admissible key

  • maxAdmissibleKey[in] Maximum admissible key

BucketPQ(uint64_t capacity, int64_t minAdmissibleKey, int64_t maxAdmissibleKey)

Builds priority queue of the specified capacity capacity.

~BucketPQ() override = default

Default destructor

void insert(int64_t key, index value) override

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

std::pair<int64_t, index> getMin()

Returns the element on top of the PrioQ.

virtual std::pair<int64_t, index> extractMin() override

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

void changeKey(int64_t newKey, index 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

Number of elements in PQ.

virtual bool empty() const noexcept override

Whether or not the PQ is empty.

bool contains(const index &value) const override

Whether or not the PQ contains the given element.

void remove(const index &val) override

Removes key-value pair given by value val.

virtual int64_t getKey(const index &val)

key to given value @val.