Ora che abbiamo alberi Black Red e alberi AVL, significa che gli inserimenti e le eliminazioni richiedono log (N). (Notiamo anche che find_min () accetta il log (N)).
Confrontandoli per accumulare, abbiamo le stesse complessità. Tuttavia gli alberi sopra menzionati sono BST, quindi possiamo cercare nel registro (N) lì. Tutto sommato non capisco come gli heap possano essere utili?
Un mucchio è sempre perfettamente bilanciato. Un albero Black Red è vincolato da quanto può essere sbilanciato, ma sarà comunque spesso meno perfettamente bilanciato. Sebbene ciò non influenzi il valore Big O delle operazioni, ciò non significa che non ci sia una differenza di prestazioni; c'è una molto vasta gamma di prestazioni possibili tra qualsiasi dato valore di Big O, e i miglioramenti all'interno di tale intervallo sono ancora molto spesso utili nell'applicazione pratica.
Leggi altre domande sui tag data-structures heap