Implementazione della coda di priorità utilizzando l'heap massimo rispetto a BST bilanciato

Question

BST bilanciato e heap max eseguono sia l'inserimento che l'eliminazione in O(logn). Tuttavia, trovare il valore massimo in un heap massimo è O(1)ma questo è O(logn)in BST bilanciato.

Se rimuoviamo il valore massimo in un heap massimo, ci vuole O(logn)perché è un'operazione di cancellazione.

In BST bilanciato, eliminare l'elemento max = trovare il valore massimo + eliminare; è uguale a logn + logn si riduce a O(logn). Quindi anche l'eliminazione del valore massimo in BST bilanciato è O(logn).

Ho letto che una di queste applicazioni di max heap è una coda di priorità e il suo scopo principale è rimuovere il valore massimo per ogni operazione di rimozione dalla coda . Se l'eliminazione di max element è O(logn)sia per max heap che per BST bilanciato, ho le seguenti domande

• Qual è lo scopo di un heap massimo nella coda di priorità solo perché è facile da implementare anziché utilizzare BST bilanciato con ricerca completa?

• Poiché non esiste un calcolo del fattore di bilanciamento, l'heap massimo può essere definito un albero binario sbilanciato?

• Ogni BST bilanciato può essere utilizzato come coda prioritaria e quale è anche ricercabile in O(logn)quanto la ricerca max heap è O(n)corretta?

Tutte le complessità temporali vengono calcolate per il caso peggiore. Qualsiasi aiuto è molto apprezzato.

Answer 1

Qual è lo scopo di un heap massimo nella coda di priorità solo perché è facile da implementare anziché utilizzare BST bilanciato con ricerca completa?

Alcuni vantaggi di un heap sono:

• Dato un array di input non ordinato, un mucchio può ancora essere costruito in O (n) tempo , mentre un BST necessita O (nlogn) tempo .

• Se l'input iniziale è un array, lo stesso array può fungere da heap, il che significa che non è necessaria alcuna memoria aggiuntiva. Sebbene si possa pensare a modi per creare un BST utilizzando i dati sul posto nell'array, sarebbe piuttosto strano (per i tipi primitivi) e darebbe più overhead di elaborazione. Un BST viene solitamente creato da zero, copiando i dati nei nodi man mano che vengono creati.

  Fatto interessante: un array ordinato è anche un heap, quindi se è noto che l'input è ordinato, non è necessario fare nulla per creare l'heap.

• Un heap può essere memorizzato come un array senza la necessità di memorizzare riferimenti incrociati , mentre un BST di solito è costituito da nodi con riferimenti sinistro e destro. Ciò ha almeno due conseguenze:

  • La memoria utilizzata per un BST è circa 3 volte maggiore di quella per un heap.
  • Sebbene diverse operazioni abbiano la stessa complessità temporale sia per l'heap che per il BST, il sovraccarico per l'adattamento di un BST è molto maggiore, quindi il tempo effettivo impiegato su queste operazioni è un fattore (costante) maggiore nel caso BST.

Poiché non esiste un calcolo del fattore di bilanciamento, l'heap massimo può essere definito un albero binario sbilanciato?

Un mucchio è infatti un albero binario completo , quindi è sempre il più equilibrato possibile: le foglie saranno sempre posizionate nell'ultimo o nell'ultimo livello. Un BST autobilanciato (come AVL, rosso-nero, ...) non può battere quell'alto livello di bilanciamento, dove spesso avrai foglie che si verificano a tre livelli o anche di più.

Ogni BST bilanciato può essere utilizzato come coda prioritaria e che è anche ricercabile in O (logn), tuttavia la ricerca max heap è O (n) corretta?

Si è vero. Quindi, se l'applicazione necessita della funzione di ricerca, allora un BST è superiore.

Answer 2

Qual è lo scopo di un heap massimo nella coda di priorità solo perché è facile da implementare anziché utilizzare BST bilanciato con ricerca completa?

No. Max heap si adatta meglio, poiché è accuratamente strumentato per restituire l'elemento successivo (rispettando la priorità) al più presto, in tempo O (1). Questo è quello che vuoi dalla coda di priorità più semplice possibile.

Poiché non esiste un calcolo del fattore di bilanciamento, l'heap massimo può essere definito un albero binario sbilanciato?

No. C'è anche un equilibrio. Per farla breve, il bilanciamento di un mucchio viene eseguito da operazioni di spostamento verso l'alto o verso il basso (scambio di elementi che sono fuori servizio).

Ogni BST bilanciato può essere utilizzato come coda prioritaria e che è anche ricercabile in O (logn), tuttavia la ricerca max heap è O (n) corretta?

Si! Così come l'elenco collegato potrebbe essere utilizzato o array. Sarà solo più costoso in termini di notazione O e molto più lento nella pratica.