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.
CodePudding user response：
std::priority_queue is a container adapter that turns the provided container meeting very specific requirements (your std::vector) into an implementation of the abstract data structure priority queue, one possible implementation of which is a heap.
Strictly speaking, priority queues do not have to look like heaps, but in the case of C std::priority_queue, the standard makes it very hard not to expect that the underlying container is turned into a heap. The standard specifies that the container support front(), push_back(), and pop_back() and have random access iterators; precisely those needed to implement heap algorithms such as make_heap(), push_heap(), and pop_heap(). The standard also requires these heap functions to be implemented and further that the std::priority_queue member functions have the exact effects of using them!
So the standard does not require that std::vector is turned into a heap, but it is difficult to imagine having the heap utilities and NOT using them on std::priority_queue's std::vector (or std::deque) to make a heap.
If it quacks like a duck...
CodePudding user response：
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();