Coda di priorità modificata (con elementi "disattivati")

0

Ho bisogno di qualcosa come una coda di priorità ma con la seguente modifica:

A volte ho bisogno di contrassegnare alcuni elementi nella coda come "disabilitati".

Elementi disabilitati:

  1. temporaneamente (finché non viene contrassegnato come non disabilitato) diventa meno prioritario rispetto a qualsiasi elemento non disabilitato;

  2. non vengono mai estratti dalla coda. Questo è se l'algoritmo della coda di priorità conduce (poiché tutti gli elementi non disabilitati sono "esauriti" (già spuntati)) in spuntando un elemento disabilitato, si comporta come se la coda fosse vuota e invece genera un'eccezione.

Qual è il modo consigliato per implementarlo? Conosco solo la seguente soluzione: Metti tutti gli elementi in una lista / vettore di conseguenza l'ordine in cui arrivano e fai un pop (facendo una ricerca O (N)) di conseguenza la priorità dall'elenco ogni volta che viene richiesto. Questa potrebbe non essere la soluzione più efficiente. È un modo abbastanza semplice per farlo in modo più efficiente?

In effetti, ho bisogno di una coda con priorità doppia (modificata). Scrivo in Python.

Sarebbe troppo prolisso per spiegare la situazione reale di cui ho bisogno, ma è parte di questo grande progetto: link

    
posta porton 02.05.2018 - 17:33
fonte

1 risposta

2

Si suppone che una coda di priorità venga mantenuta ordinata. Se gli elementi cambiano la loro priorità (muting) mentre sono in coda, non verranno utilizzati perché la coda non ha idea di essere cambiati.

Sono riluttante a fare previsioni di efficienza senza un test ma delle due soluzioni che vedo:

  1. Rimuovi, muta, spinge (innescando l'ordinamento), rileva magicamente come disabilitato prima di scoppiare.
  2. Rimuovi, passa a una coda diversa denominata disabilitata.

2 sembra il modo migliore per andare.

    
risposta data 02.05.2018 - 17:44
fonte

Leggi altre domande sui tag