CODEWITHSUNDEEP
c++priority-queueheap
PhiloRobotist
PhiloRobotist

Reputation: 337

Should the underlying container of a priority_queue be considered a complete binary tree?

Say I'm using a std::vector as the underlying container of a std::priority_queue.

Should I consider this vector as a representation of a binary heap (Becz., a priority_queue is similar to a heap (Am I right in this assumption? An awful lot of sources on the web use these 2 terms interchangeably)? or is it just a normal vector?

By "representation of a binary heap" I mean -> 0th element of the vector is the root of the bin. heap, 1st element is the left child of the root, 2nd element is the right child & so on.

Upvotes: 0

Views: 149

Answers (1)

Caleth
Caleth

Reputation: 62576

Yes, the standard mandates that the member functions of priority_queue have the same effect as applying the relevant heap operation to the underlying container:

void push(const value_type& x);

Effects: As if by:

c.push_back(x); 
push_heap(c.begin(), c.end(), comp);

void push(value_type&& x);

Effects: As if by:

c.push_back(std::move(x)); 
push_heap(c.begin(), c.end(), comp);

template<container-compatible-range<T> R> void push_range(R&& rg);

Effects: Insert all elements of rg in c.

Postconditions: is_­heap(c.begin(), c.end(), comp) is true.

template<class... Args> void emplace(Args&&... args);

Effects: As if by:

c.emplace_back(std::forward<Args>(args)...); 
push_heap(c.begin(), c.end(), comp);

void pop();

Effects: As if by:

pop_heap(c.begin(), c.end(), comp); 
c.pop_back();

priqueue.members

Because the underlying container is a protected member, and access controls apply to naming the member, you can get at any priority_queues data, even if it isn't a base-subobject of a class you've defined.

template <typename T, typename Container, typename Comp>
const Container & get_container(const std::priority_queue<T, Container, Comp> & queue) {
    struct access_t : std::priority_queue<T, Container, Comp> {
        auto member_ptr() { return &access_t::c; }
    } access;
    auto ptr = access.member_ptr();
    return queue.*ptr;
}

Upvotes: 1

Related Questions