Sto rivedendo i miei appunti sull'algoritmo di Kruskal e ho una domanda su come portare il tempo di esecuzione a O (E lg V). Usando un PQ con bordi e un array booleano di cui i vertici abbiamo aggiunto al nostro albero T , il tempo di esecuzione è O (E lg E), ma nelle mie note c'è anche una variante con tempo di esecuzione O (E lg V), usando un PQ con i vertici invece dei bordi. Tuttavia, ciò richiede che il PQ supporti l'aggiornamento dei pesi (parte importante evidenziata):
Maintain a PQ of vertices connected by an edge to T, togethether with the edge that connects it to T. The priority of this tuple is the weight of the min-weight edge connecting it to T. When adding a new vertex to the tree, we add all vertices adjacent to this new vertex to the PQ unless it's already in the PQ. If it is in the PQ and the new edge connecting it to T is of lower weight, we update its weight and the edge associated with it, if not, we do nothing.
Quando ho pensato a come implementarlo, mi sono reso conto che tutte le code di priorità che ho visto hanno aggiornamenti O (n), dal momento che l'ordine è troppo debole per essere in grado di trovare un elemento più velocemente. Ho provato a cercare un po 'ma non sono riuscito a trovare nessun PQ che supporti l'aggiornamento in tempo O (lg n), ad eccezione di alcuni riferimenti agli heap di Fibonacci che possono essere eseguiti in tempo O (1), ma sembra una struttura di dati molto più complessa.
C'è un modo semplice per ottenere gli aggiornamenti di O (lg n) di una coda di priorità? Potrei inserire chiavi e riferimenti a elementi in una tabella hash e usarlo per trovare e aggiornare rapidamente gli elementi, questa è una soluzione praticabile? (Capisco che questo richiederà O (n) spazio extra.)