Nel STL C ++, priority_queue (heap) può essere utilizzato con qualsiasi contenitore sottostante, ad esempio deque . In che modo l'implementazione rimane O(log n) se deque s non scambia un elemento nell'indice a con indice b in tempo costante?
Hai ragione che non sarebbe possibile realizzare un'implementazione efficiente dell'heap in cima a una lista doppiamente collegata. Tuttavia, deque s non sono elenchi collegati doppiamente; sono contenitori ad accesso casuale . deque s è in grado di scambiare un elemento nell'indice a con indice b in tempo costante. Vedi la documentazione SGI per deque s .
Leggi altre domande sui tag c++ stl linked-list heap