Ho un vettore che voglio usare per creare un heap. Non sono sicuro se dovrei usare la funzione make_heap di C++ o mettere il mio vettore in una coda di priorità? Quale è meglio in termini di prestazioni? Quando dovrei usare l'uno contro l'altro?Quando dovrei usare make_heap rispetto a Priority Queue?
Non c'è differenza in termini di prestazioni. std::priority_queue è solo una classe dell'adattatore che racchiude il contenitore e le stesse chiamate di funzione relative all'heap in una classe. La specifica dello std::priority_queue dichiara apertamente che.
Creando una coda di priorità basata sull'heap da un esposto std::vector (richiamando direttamente le funzioni relative all'heap) si mantiene aperta la possibilità di accesso esterno, potenzialmente danneggiando l'integrità dell'heap/coda. std::priority_queue funge da barriera che limita l'accesso a un minimo "canonico": push(), pop(), top() ecc. Si può vedere come misura di imposizione di autodisciplina.
Inoltre, adattando l'interfaccia della coda al set di operazioni "canoniche", è possibile renderlo uniforme e intercambiabile con altre implementazioni basate sulla classe di code di priorità conformi alla stessa specifica esterna.
Un priority_queue è (almeno normalmente) implementato come heap. In quanto tale, la vera domanda è se un priority_queue fornisce ciò di cui hai bisogno. Quando usi make_heap hai ancora accesso a tutti gli elementi. Quando usi priority_queue, hai solo poche operazioni che danno accesso molto limitato agli elementi (in pratica basta inserire un elemento e rimuovere l'elemento in testa alla coda).
priority_queue non è un contenitore. Si tratta di un adattatore contenitore che utilizza uno specifico contenitore sottostante, ad es. vector o deque e fornisce un insieme specifico di metodi per lavorare con i dati. Inoltre, la sua implementazione si basa sugli algoritmi *_heap.
Ad esempio, ogni volta che si preme un nuovo valore su vector, è necessario chiamare push_heap per estendere un intervallo considerato come heap. Se non si utilizza priority_queue, è possibile considerare, ad esempio, una metà dello vector come heap (std::make_heap(v.begin(), v.begin() + (v.size()/2))), mentre un'altra metà sarà così com'è.
Cosa priority_queue fa quando si chiama push su di esso: si spinge un nuovo elemento alla parte posteriore del contenitore sottostante e invita push_heap di mantenere la proprietà di heap priorità (conta solo il primo elemento ad essere il più grande).
Direi che è meglio prendere in considerazione la progettazione della soluzione e le esigenze specifiche, piuttosto che i problemi di prestazioni.
Se non si desidera modificare tale vettore, è necessario utilizzare la coda di priorità mentre crea un vettore separato (richiede spazio aggiuntivo). Inoltre, è facile da implementare. Ad esempio, quando usi make_heap mentre fai scoppiare un elemento devi usare due comandi, prima pop_heap e poi pop_back .. ma puoi farlo con un solo comando in caso di coda di priorità. Allo stesso modo, mentre si spinge l'elemento nell'heap.
Ora, la performance di entrambi sarebbe la stessa perché la coda di priorità non è un contenitore e utilizza un contenitore sottostante come vettore o deque che usa le stesse operazioni di heap usate dalle operazioni make_heap. Quindi, dovresti usarne una in base al tuo requisito .
beh, se si desidera un heap, è necessario trasformarlo in un heap. Le code prioritarie non sono tutti heap. Gli heap tendono a comportarsi meglio. – Wug