Differenza tra std :: set e std :: priority_queue

Question

Poiché sia ​​std::priority_queue e std::set (e std::multiset) sono contenitori di dati che memorizzano gli elementi e consentono di accedervi in ​​modo ordinato e hanno la stessa complessità di inserimento O(log n), quali sono le vantaggi dell'utilizzo dell'uno sull'altro (o, che tipo di situazioni richiedono l'uno o l'altro?)?

Anche se so che le strutture sottostanti sono diverse, non sono tanto interessati alla differenza nella loro attuazione, come io sono in confronto loro prestazioni e idoneità per vari usi.

Nota: Conosco i non duplicati in un set. Ecco perché ho anche menzionato lo std::multiset poiché ha lo stesso identico comportamento dello std::set ma può essere usato dove i dati memorizzati possono essere paragonati come elementi uguali. Quindi, per favore, non commentare il problema delle chiavi singole/multiple.

Answer 1

Una priorità coda solo permette di accedere a una elemento in modo ordinato - vale a dire, è possibile ottenere l'oggetto massima priorità, e quando si rimuove questo, si può ottenere la priorità più alta, e così via. Una coda di priorità consente anche elementi duplicati, quindi è più simile a un multiset che a un set. [Modifica: come sottolineato da @Tadeusz Kopec, la creazione di un heap è anche lineare sul numero di elementi nell'heap, dove la creazione di un set è O (N log N) a meno che non venga costruita da una sequenza già ordinata (nel qual caso è anche lineare).

Un set consente l'accesso completo in ordine, in modo tale da poter trovare, ad esempio, due elementi da qualche parte nel mezzo del set, quindi passare in ordine da uno all'altro.

Answer 2

set/multiset sono generalmente supportati da un albero binario. http://en.wikipedia.org/wiki/Binary_tree

priority_queue è generalmente supportato da un heap. http://en.wikipedia.org/wiki/Heap_(data_structure)

Quindi la domanda è davvero quando dovresti usare un albero binario invece di un mucchio?

Entrambe le strutture sono disposte su un albero, tuttavia le regole relative alla relazione tra gli aneddori sono diverse.

Chiameremo le posizioni P per genitore, L per bambino sinistro e R per bambino destro.

In un albero binario L < P < R.

In un mucchio P < L e P < R

alberi binari Quindi sorta "lateralmente" e mucchi ordinamento "alto".

Quindi se guardiamo a questo come un triangolo che nell'albero binario L, P, R sono completamente ordinati, mentre nell'heap la relazione tra L e R è sconosciuta (solo la loro relazione con P).

Questo ha i seguenti effetti:

• Se si dispone di un array misti e vuole trasformarlo in un albero binario ci vuole O(nlogn) tempo. Se si vuole trasformarlo in un cumulo ci vuole solo O(n) tempo, (come si confronta solo per trovare l'elemento estremo)

• Cumuli sono più efficienti se avete solo bisogno l'elemento estremo (più basso o più alto da qualche funzione di confronto). Gli heap effettuano solo i confronti (pigramente) necessari per determinare l'elemento estremo.

• Gli alberi binari eseguono i confronti necessari per ordinare l'intera raccolta e mantengono l'intera raccolta ordinata tutto il tempo.

• Gli heap hanno una ricerca a tempo costante (sbirciatina) dell'elemento più basso, gli alberi binari hanno la ricerca del tempo logaritmico dell'elemento più basso.

Answer 3

std::priority_queue permette di effettuare le seguenti operazioni:

1. Inserire un elemento O(log n)
2. Prendi l'elemento più piccoloO(1)
3. Cancellare l'elemento più piccoloO(log n)

mentre std::set hapiù possibilità:

1. inserire qualsiasi elemento O(log n) e la costante è maggiore che in std::priority_queue
2. Trova qualsiasi elemento O(log n)
3. trovare un elemento,> = di quello che state cercando O(log n) (lower_bound)
4. Erase qualsiasi elemento O(log n)
5. Passare alla precedente successivo elemento/in modo ordinato O(1)
6. Prendi l'elemento più piccoloO(1)
7. Prendi l'elemento più grandeO(1)

Answer 4

Dato che sia std::priority_queue e std::set (e std::multiset) sono contenitori di dati che memorizzano gli elementi e permettono di accedervi in modo ordinato e con la stessa complessità di inserimento O(log n), quali sono i vantaggi dell'utilizzo di uno sull'altro (o, che tipo di situazioni richiedono l'uno o l'altro?)?

Anche se inserto e cancelli operazioni per entrambi i contenitori hanno la stessa complessità O (log n), queste operazioni per std :: set risultano inferiori rispetto a std :: priority_queue . Questo perché std :: set rende molte allocazioni di memoria.Ogni elemento di std :: set viene memorizzato nella propria allocazione. std :: priority_queue (con sottostrato std :: vector contenitore per impostazione predefinita) utilizza l'allocazione singola per memorizzare tutti gli elementi. D'altra parte std :: priority_queue utilizza molte operazioni di scambio sui suoi elementi mentre std :: set utilizza solo lo scambio di puntatori. Quindi se lo swapping è un'operazione molto lenta per il tipo di elemento, usare std :: set potrebbe essere più efficiente. Inoltre, l'elemento potrebbe non essere affatto scambiabile.

Memory overhead per std :: set è molto più grande anche perché deve memorizzare molti puntatori tra i suoi nodi.