Ho una coda di priorità degli eventi, ma a volte le priorità degli eventi cambiano, quindi mi piacerebbe mantenere gli iteratori dai richiedenti dell'evento nell'heap. Se la priorità cambia, mi piacerebbe che l'heap fosse regolato nel tempo log (n). Avrò sempre esattamente un iteratore che punta a ciascun elemento nell'heap.Esiste una classe heap in C++ che supporti la modifica della priorità di elementi diversi dalla testa?
Sono felice di segnalare che Boost ora ha aggiunto uno Boost.Heap library con un numero di stellar data structures.
Il vantaggio di questo è che gli heap di Fibonacci supportano la modifica della priorità in tempo di ammortamento costante.
Sfortunatamente, tutti gli heap mutabili sono basati su nodi (in altre parole, hanno un'indirizzamento extra come suggerito da @wilx). @ La risposta di Feruccio agli "ammassi mutabili" di Boost ha un codice che permette di scrivere ammassi mutevoli basati su vettori se sei disposto ad avere dei puntatori alle maniglie contenute nel tuo tipo di valore.
Sembra che tu abbia bisogno di più indirezione. Memorizza il puntatore agli eventi nella coda di priorità. Quando la priorità di alcuni elementi della coda cambia, rimuoverla e reinserirla.
Dai uno sguardo a Boost's mutable heaps.
Un avvertimento è che si finisce con l'evento instabile l'ordinamento, cioè ordinamento degli eventi con la stessa priorità non è definito (leggi 'saranno riordinati'.)
È possibile rimuovere un elemento arbitrario da un heap nel tempo log (n). –
Sì, hai ragione, stava pensando a qualcos'altro :) –
nessun problema :) –
Grazie, se finisco per dover stampare il mio, userò lo snippet per iniziare. –
è finito con questa soluzione –
@Ferruccio Grazie, ho salvato i miei buoni 45 minuti e alcuni bug. –