1. Che cos'è una Coda di Priorità?
Una coda di priorità (Priority Queue) è una struttura dati astratta simile a una coda o a uno stack classico, in cui ciascun elemento possiede un valore numerico o logico associato detto priorità.
A differenza delle code FIFO standard, l'elemento che viene rimosso per primo non è quello arrivato prima temporalmente, ma quello con la priorità più alta (o più bassa, a seconda delle convenzioni implementative). Se due elementi condividono la stessa priorità, solitamente si ricorre al criterio standard FIFO.
2. Principali Operazioni e Strategie
Le funzioni fondamentali supportate da una coda di priorità sono:
- Insert / Enqueue(valore, priorita): Inserisce un nuovo elemento all'interno della struttura associandogli il rispettivo livello di priorità.
- Pull / ExtractMax (o ExtractMin): Rimuove e restituisce l'elemento con la priorità massima o minima presente nella struttura.
- Peek: Ispeziona l'elemento con la priorità maggiore senza rimuoverlo.
- Array o Lista non ordinata: Inserimento efficiente in $\mathcal{O}(1)$, ma estrazione lenta $\mathcal{O}(N)$ poiché bisogna scorrere tutti i nodi per trovare il massimo.
- Array o Lista ordinata: Estrazione rapida $\mathcal{O}(1)$, ma inserimento oneroso $\mathcal{O}(N)$ per mantenere l'ordine.
- Binary Heap (Mucchio Binario): La soluzione ideale e più diffusa, che garantisce sia inserimento che estrazione in tempo logaritmico $\mathcal{O}(\log N)$.
3. Simulatore Interattivo: Coda di Priorità
Testa l'inserimento con priorità: gli elementi si posizionano automaticamente ordinati dal più urgente al meno urgente.