Class BucketPQ¶

Nested Relationships¶

Inheritance Relationships¶

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.

Parameters:

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

Returns:

Number of elements in PQ.

virtual bool empty() const noexcept override¶

Returns:

Whether or not the PQ is empty.

bool contains(const index &value) const override¶

Returns:

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

Returns:

key to given value @val.