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?
You are right that it would not be possible to make an efficient heap implementation on top of a doubly linked list. However,