Il motivo dell'uso di `std :: greater` per la creazione di heap minimo tramite` priority_queue`

Question

Mi chiedo perché per la creazione di un heap minimo utilizzando priority_queue, è necessario utilizzare std::greater?

std::priority_queue<T, std::vector<T>, std::greater<T> > min_heap; 

Per me, dal momento che il valore più piccolo si trova sempre in cima al mucchio, la classe impiegato dovrebbe essere std::less

Aggiornamento: D'altra parte, dal momento che il comportamento predefinito di priority_queue (max heap) è quello di tenere il più grande valore in alto, mi sembra che la std::greater dovrebbe essere utilizzato per la creazione max heap e non per la creazione mucchio min

Answer 1

L'argomento logico è come segue

1. std::priority_queue è un adattatore contenitore; considerazioni di memoria di base rendono la parte posteriore il luogo preferito per le modifiche (con pop_back() e push_back()) per contenitori sequenza come std::vector.
2. i priority_queue primitive sono basati su std::make_heap (costruttore), std::pop_heap + container::pop_back (priority_queue::pop) e container::push_back + std::push_heap (priority_queue::push)
3. pop_heap prenderà il fronte dello stoccaggio sottostante e metterlo a posteriore, ripristinando in seguito l'invariante dell'heap. Il contrario va per push_heap.
4. facendo sort_heap su un max_heap (con il massimo nella parte anteriore inizialmente) sarà repeatedly pop the front to the back ed ordinare della gamma secondo less (che è l'operatore di confronto predefinito)
5. conseguenza, la realizzazione preferita di un max_heap è di avere il massimo elemento wrt less nella parte anteriore, accessibile tramite priority_queue::top (sottostante container::front).
6. si può ancora discutere se sia intuitivo che priority_queue con un comparatore std::less rappresenti un max_heap. Potrebbe essere stato definito come min_heap invertendo gli argomenti del comparatore (ma si veda il commento di @ T.C. Che con i rilegatori C++ 98 questo è piuttosto prolisso) ovunque nelle chiamate alle varie funzioni di heap. L'uno (per me) risultato contro-intuitivo che sarebbe stato top() sarebbe allora non hanno dato l'elemento con top priorità

Answer 2

le funzioni di heap C++ make_heap, push_heap e pop_heap operano su un max heap, il che significa che l'elemento superiore è massimo quando si utilizza il comparatore predefinito. Quindi, per creare un min-heap, è necessario utilizzare greater<T> anziché less<T>.

Sospetto che un heap massimo sia utilizzato al posto di un heap minimo è che è più facile da implementare con l'operazione less. In C++, less ha il privilegio speciale di essere il tipo di comparatore "predefinito" per tutti gli algoritmi STL; se si prevede di implementare solo un'operazione di confronto (diversa da ==), dovrebbe essere <. Questo porta alla sfortunata stranezza che priority_queue<T, C<T>, less<T>> significa una max-queue e priority_queue<T, C<T>, greater<T>> significa una coda minima.

Inoltre, alcuni algoritmi come nth_element richiedono un heap massimo.

Answer 3

Vedere http://en.cppreference.com/w/cpp/container/priority_queue. A priority_queue è progettato per mettere il più grande valore in alto. Ciò accade se si utilizza il comparatore di default std::less. Quindi, se si desidera il comportamento inverso, è necessario utilizzare il comparatore inverso, std::greater.