4
votes
1answer
313 views

How does a priority_queue maintain a heap on a deque efficiently?

In the C++ STL, priority_queue (heap) can be used with any underlying container, such as a deque. How does the implementation stay O(log n) if deques don't swap an item in index a with index b in ...