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.