Implementazione di una coda di priorità con un array circolare

Il problema con l'uso di un array (circolare o meno) come struttura dati sottostante per una coda di priorità è che devi sempre copiare gli elementi per creare un buco dove inserire un nuovo elemento o per riempire il buco creato rimuovendo un elemento.

In un'implementazione molto ingenua, usando il tuo array circolare, potresti usare il seguente schema:

• Quando aggiungi un elemento, aggiungilo sempre nella posizione indicata da next e incrementa next .
• Quando rimuovi un elemento, copia l'elemento indicato da first nella posizione appena liberata e incrementa first .

Questo schema è facile da implementare, ma presenta il grande svantaggio che è necessario eseguire il ciclo sull'intera (parte utilizzata della) matrice per trovare l'elemento con la massima priorità.
Per gli esercizi di apprendimento, questo non è un grosso problema, ma sicuramente lo si vuole evitare nel codice di produzione.

Nel codice di produzione, è preferibile utilizzare una struttura dati che viene continuamente ordinata sulla priorità degli articoli, in modo che l'elemento con la priorità più alta sia sempre in primo piano. Questo può essere fatto con array (preferibilmente array normali, non circolari) o liste collegate. Gli elenchi collegati possono avere un vantaggio in termini di prestazioni perché è più semplice aggiungere elementi al centro e rimuovere il primo elemento senza dover toccare un gruppo di altri elementi.

Come semplice fix puoi scambiare l'elemento max con first e poi pop normalmente.

Tuttavia, ti suggerisco di utilizzare una struttura max-heap . Questo ha il vantaggio di avere solo O(log n) di complessità temporale per push e pop e può adattarsi alla matrice di dimensioni fisse.

Inserire un valore implica mettere l'ultimo elemento nella testa e spostarlo verso il basso. Spingere un valore comporta spingere alla fine e spostarlo verso l'alto (o spostando ricorsivamente il genitore diretto verso il basso finché non è al suo posto).

Non usare affatto un array circolare. È molto più semplice ed efficiente usare semplicemente un array regolare in cui si riempiono gli spazi scambiando con il valore più arretrato dell'array e si manipola solo l'indice finale quando si aggiungono o rimuovono elementi.

Come detto da altri, un heap binario è il modo standard per implementare una coda di priorità e trarrai vantaggio da questa stessa strategia di sovrascrittura-rimozione quando implementerai un heap binario.

push (int i) {
  // Make sure it's not full first!
  array[end_index++] = i;
}

int pop () {
  // Make sure it's not empty first!
  // Set max_index to index the maximum value
  int result = array[max_index];
  array[max_index] = array[--end_index];
}