Qual è la complessità temporale dell'aggiornamento nell'heap binario?

6

Per un heap binario abbiamo O (log (n)) per l'inserimento, O (log (n)) per eliminare min e la costruzione dell'heap può essere eseguita in O (n).

Nel contesto dell'utilizzo di un heap binario in Djikstra, il mio esame ha coinvolto un "aggiornamento" nell'heap in cui è stata modificata la priorità di un vertice.

Supponevo che la complessità temporale di questo aggiornamento sarebbe stata O (n) poiché mi sembrava che localizzare il vertice nell'heap richiedesse qualcosa nell'ordine di una ricerca lineare, seguita da una svolta o downheap. Questo sarebbe O (n + log (n)) che è semplicemente O (n).

Purtroppo penso che questo mi ha portato alla risposta sbagliata.

Quindi, qual è la complessità temporale attuale di un aggiornamento prioritario in un heap binario?

    
posta Brendan Hill 16.11.2015 - 07:56
fonte

2 risposte

6

La chiave per risolvere il tuo problema è restituire un oggetto speciale sull'inserimento di un elemento. Quando sposti l'oggetto reale nell'heap, aggiorni la posizione in questo oggetto.

Per chiamare la priorità di riduzione, si passa questo oggetto in modo da poter andare direttamente alla posizione nell'heap e creare un fumetto dell'elemento, se necessario.

In questo modo è O (log (n)). Infatti trovare l'elemento è O (1) e il ripristino della proprietà heap è O (log (n)).

P.S. Dovresti controllare se la nuova priorità effettivamente diminuisce.

    
risposta data 16.11.2015 - 09:07
fonte
2

Non accetto un po 'di disaccordo con Scara95 . Con fuori contesto della tua risposta questo sembra che la tua risposta sia sbagliata o meno potrebbe essere una questione di pedanteria. Tecnicamente, sì, non è O (N) + O (log (N)) perché è possibile trovare la posizione degli elementi in un tempo costante. Tuttavia, ciò richiede una struttura dati completamente diversa per andare insieme al tuo heap binario . Devi mappare gli elementi inseriti in una tabella hash , in modo tale che quando inserisci elementi nella priorità, inserisci anche una nuova voce nella tabella hash, un hash unico dell'elemento che hai appena inserito, con la posizione come valore.

Per aggiornare, interrogare la tabella hash con l'ID dell'elemento nella coda di priorità che si desidera aggiornare e acquisire il valore degli elementi di hashtable per scoprire dove aggiornare l'elemento della coda di priorità, dove si percula su / heapify up / giù

Ma a questo punto, non si ha più solo un heap binario, si ha un heap binario e una tabella hash, probabilmente una nuova struttura dati in quanto le effettive funzioni per aggiornare l'heap non possono essere separate dai due dati -Strutture. È possibile implementare gli heap binari in cui la complessità dell'aggiornamento non può essere migliore di O (N) dato che semplicemente non si include una tabella hash. Spesso si trovano anche documenti su nuovi algoritmi / strutture di dati sono in realtà le stesse strutture di dati, ma con nuove componenti spesso altre strutture di dati si mescolano nello stesso modo in cui dovrebbe essere il tavolo hash, quindi questo rende l'intero esercizio ancora più confuso.

La linea di fondo è che se la domanda ti chiedesse quale sarebbe la migliore complessità di aggiornamento possibile per un heap binario, la tua risposta era sbagliata, nessuna domanda, ma se la domanda fosse più specifica in termini di ciò di cui avete parlato ragazzi in classe, parlando di un mucchio binario formato in un modo specifico, le cose diventano molto più complicate.

    
risposta data 29.01.2018 - 21:08
fonte

Leggi altre domande sui tag