Mucchio o albero rosso-nero?

Question

Sono disposto ad utilizzare una struttura dati come buffer di overflow di spazio costante. Voglio avere un inserto efficiente ma soprattutto una rimozione efficiente dell'elemento min. Stavo pensando di utilizzare un heap dal momento che ho O (log (n)) find_min() e log (n) inserimento e cancellazione. D'altra parte so che non capisco il vantaggio rispetto ad un albero rosso-nero visto che ha anche O (log (n)) insert e delete ma e O (1) find min/max. E il vantaggio dell'output ordinato (non mi interessa).

La domanda è legata a: Is a red-black tree my ideal data structure?

Dal momento che ho entrambe le strutture disponibili da std :: map e da boost :: mucchio perché dovrei preferire usare mucchio anziché l'albero rosso-nero? Infine, usando l'albero rosso-nero ho anche O (log (n)) tempo di ricerca per una voce mentre per un heap il tempo è O (n) che è importante poiché i duplicati esistono.

Answer 1

La differenza riguarda principalmente le modalità di utilizzo delle strutture.

• cumuli binari sono strutture di dati molto veloci per inserire valori e recuperare il valore minimo. Tuttavia, non supportano la ricerca efficiente o la cancellazione di valori casuali.

• Gli alberi rossi/neri sono alberi di ricerca binari bilanciati che supportano l'inserimento efficiente, la cancellazione, la ricerca di valori arbitrari e (ragionevolmente veloce) la ricerca-minima. Tuttavia, hanno un sovraccarico rispetto a un heap binario.

Se tutto ciò che serve è l'inserimento, find-minimo, e rimuovere-minima, l'heap binario è probabilmente una scelta superiore, perché il sovraccarico è inferiore e il tempo di esecuzione dovrebbe essere più veloce. Se è necessario inserire e rimuovere valori arbitrari o cercare valori arbitrari, l'albero rosso/nero è probabilmente la scelta migliore. Come per tutti gli aspetti ingegneristici, la scelta della struttura dei dati corretta è incentrata sui compromessi.

Inoltre, si noti che è possibile utilizzare std::priority_queue se è necessario un heap binario; non è necessario utilizzare Boost. Non è inoltre garantito che std::map sia un albero rosso/nero; è probabilmente una sorta di BST bilanciato, ma potrebbe essere bilanciato usando qualche altro algoritmo.

Spero che questo aiuti!

Answer 2

Un heap è facilmente implementabile nella memoria contigua, cioè una matrice. Un albero rosso-nero viene in genere costruito con un'allocazione heap separata per ogni nodo. L'albero rosso-nero finisce per accedere alla memoria su tutto l'heap per ogni attraversamento dell'albero. Questo è il comportamento della cache nel caso peggiore. Anche se la complessità algoritmica di alcune operazioni è la stessa per entrambe le strutture, l'overhead costante per l'albero rosso-nero è molto più alto.