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

Question

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 constant time?

Answer 1

You are right that it would not be possible to make an efficient heap implementation on top of a doubly linked list. However, deques aren't doubly linked lists; they are random access containers. deques are able to swap an item in index a with index b in constant time. See the SGI documentation for deques.