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?

Deque stands for double-ended-queue. – Brian Jan 14 '13 at 15:35 — Brian, Jan 14 '13 at 15:35

score 10 · Accepted Answer · answered Jan 14 '13 at 06:53

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.

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

1 Answers1